2018-2019 ACM-ICPC, Asia Seoul Regional Contest K - TV Show Game

問題ページ
2SATで解く． 番目の電球がBならtrue というbool変数を用意する．例えば，1 R 2 B 3 R が与えられたとする．このとき ( or ) and ( or ) and ( or ) を満たす真偽値の組合せが存在すればよい．これはSCCを用いると で解ける．

#include "iostream"  
#include "climits"  
#include "list"  
#include "queue"  
#include "stack"  
#include "set"  
#include "functional"  
#include "algorithm"  
#include "string"  
#include "map"  
#include "unordered_map"  
#include "unordered_set"  
#include "iomanip"  
#include "cmath"  
#include "random"  
#include "bitset"  
#include "cstdio"  
#include "numeric"  
#include "cassert"  
#include "ctime"  
   
using namespace std;  
using ll = long long int;  
#define FOR(i,a,n) for(ll i=(ll)a; i<(ll)n; ++i)  
#define REP(i,n) FOR(i,0,n)  
   
struct SCC{  
    int V, K;  
    vector<vector<int>> G;  
    vector<vector<int>> rG;  
    vector<int> vs;  
    vector<int> used;  
    vector<int> cmp;  
    SCC() {}  
    SCC(int V_) : V(V_), G(V_), rG(V_), used(V_), cmp(V_) {}  
    void add_edge(int from, int to) {  
        G[from].push_back(to);  
        rG[to].push_back(from);  
    }  
    void dfs(int v) {  
        used[v] = true;  
        for (int nx : G[v]) if (!used[nx]) dfs(nx);  
        vs.push_back(v);  
    }  
    void rdfs(int v, int k) {  
        used[v] = true; cmp[v] = k;  
        for (int nx : rG[v]) if (!used[nx]) rdfs(nx, k);  
    }  
    int scc() {  
        used.assign(V, 0); vs.clear();  
        for (int v = 0; v < V; ++v) if (!used[v]) dfs(v);  
        used.assign(V, 0);  
        int k = 0;  
        for (int i = (int)vs.size() - 1; i >= 0; --i) if(!used[vs[i]]) {  
            rdfs(vs[i], k++);  
        }  
        return K = k;  
    }  
};  
   
struct twoSAT {  
    ll n;  
    SCC graph;  
    vector<bool> ans;  
    twoSAT(ll n) : n(n), graph(n*2), ans(n) {}  
    void add(pair<ll, bool> a0, pair<ll, bool> b0) {  
        ll a = a0.first, ar = (a0.first + n) % (2 * n);  
        ll b = b0.first, br = (b0.first + n) % (2 * n);  
        if (!a0.second) swap(a, ar);  
        if (!b0.second) swap(b, br);  
        graph.add_edge(ar, b);  
        graph.add_edge(br, a);  
    }  
    bool solve() {  
        graph.scc();  
        REP(i, n) if (graph.cmp[i] == graph.cmp[n + i]) return false;  
        REP(i, n) ans[i] = graph.cmp[i] > graph.cmp[n + i];  
        return true;  
    }  
};  
   
int main(){  
    ios::sync_with_stdio(false);  
    cin.tie(0);  
   
    ll k, n;  
    cin >> k >> n;  
    twoSAT graph(k);  
    REP(i, n) {  
        vector<ll> pos(3);  
        vector<char> c(3);  
        REP(j, 3) {  
            cin >> pos[j] >> c[j];   
            pos[j]--;  
        }  
   
        pair<ll, bool> p1, p2;  
        if (c[0] == 'R') p1 = { pos[0], false };  
        else p1 = { pos[0], true };  
        if (c[1] == 'R') p2 = { pos[1], false };  
        else p2 = { pos[1], true };  
        graph.add(p1, p2);  
   
        if (c[1] == 'R') p1 = { pos[1], false };  
        else p1 = { pos[1], true };  
        if (c[2] == 'R') p2 = { pos[2], false };  
        else p2 = { pos[2], true };  
        graph.add(p1, p2);  
   
        if (c[0] == 'R') p1 = { pos[0], false };  
        else p1 = { pos[0], true };  
        if (c[2] == 'R') p2 = { pos[2], false };  
        else p2 = { pos[2], true };  
        graph.add(p1, p2);  
    }  
   
    bool ret = graph.solve();  
    if (!ret) {  
        cout << -1 << endl;  
        return 0;  
    }  
   
    string ans(k, '?');  
    REP(i, k) {  
        if (!graph.ans[i]) ans[i] = 'R';  
        else ans[i] = 'B';  
    }  
    cout << ans << endl;  
}  
``