#include #include #include #include #include #include using namespace std; // 移動元と行先と辺のコストを記録する構造体 template struct Edge { int from, to; T cost; Edge(int s, T d = 1) : to(s), cost(d) {} Edge(int f, int s, T d) : from(f), to(s), cost(d) {} bool operator<(const Edge &e) const { return cost < e.cost; } bool operator>(const Edge &e) const { return cost > e.cost; } }; template using Graph = vector< vector< Edge > >; // 強連結成分分解 // Verified: AOJ GRL_3_C (Strongly Connected Components) // Verified: ARC030 C (有向グラフ) ← 強連結を潰したグラフの構築の検証 // これは 2 回の DFS によって実現できる。 // はじめに普通の DFS をするが、その時に帰りがけ順に頂点番号の配列を作る。 // 次に、元のグラフの逆辺のみで構成されたグラフに対して、 // 帰りがけ順が遅かったものから順に DFS を行う。 // 帰りかけが遅かった頂点ほど、 DAG の先頭の強連結成分に属しているため、 // 辺を逆向きにすると、先頭の強連結成分から外に出られなくなることを利用している。 template struct GraphSCC { public: const int n; vector isthrough; vector vs, cmp; vector< vector > G, rG, H; // グラフ、逆辺グラフ、縮約後のグラフ GraphSCC(vector< vector< Edge > > &g) : n(g.size()), isthrough(n, false), cmp(n, 0), G(n), rG(n) { for(int i=0; i &vec, int cur, int k) { cmp[cur] = k; isthrough[cur] = true; vec.push_back(cur); for(size_t i=0; i, int> scc() { // 1回めのDFS for(int i=0; i > S; // 2回めのDFS for(size_t i=0; i()); SCC_dfstwo(S.back(), vs[i], k++); } } H.resize(k); fill(isthrough.begin(), isthrough.end(), false); for(size_t i=0; i G; TwoSAT(int N_) : N(N_), G(2*N_) {} int neg(int k) { return (k+N) % (2*N); } void add_edge(int u, int v) { G[u].emplace_back(v); } void add_AorB(int a, int b) { // (a or b) -> (na => b) and (nb => a) add_edge(neg(a), b); add_edge(neg(b), a); } void add_NAorB(int a, int b) { // (na or b) -> (a => b) and (nb => na) add_edge(a, b); add_edge(neg(b), neg(a)); } void add_AorNB(int a, int b) { // (a or nb) -> (na => nb) and (b => a) add_edge(neg(a), neg(b)); add_edge(b, a); } void add_NAorNB(int a, int b) { // not (a and b) -> (na or nb) // (na or nb) -> (a => nb) and (b => na) add_edge(a, neg(b)); add_edge(b, neg(a)); } void add_AnandB(int a, int b) { add_NAorNB(neg(a), neg(b)); } vector build() { GraphSCC<> scc(G); vector group, res(N); int K; tie(group, K) = scc.scc(); for(int i=0; i group[N+i]); } return res; } }; void yuki_274() { int N, M; scanf("%d%d", &N, &M); vector L(N), R(N); auto flip = [&](int l, int r) { return make_pair(M - 1 - r, M - 1 - l); }; auto intersect = [&](int al, int ar, int bl, int br) { return !(ar < bl or br < al); }; for(int i=0; i NA or NB tsat.add_NAorNB(i, j); break; case 1: // NA and B はダメ -> A or NB tsat.add_AorNB(i, j); break; case 2: // A and NB はダメ -> NA or B tsat.add_NAorB(i, j); break; case 3: // NA and NB はダメ -> A or B tsat.add_AorB(i, j); break; } } } } } auto res = tsat.build(); if(res.size() == N) puts("YES"); else puts("NO"); } void yuki_470() { int N; cin >> N; vector U(N); for(int i=0; i> U[i]; if(N > 52) { cout << "Impossible" << endl; return; } TwoSAT tsat(N); for(int i=0; i res = tsat.build(); if(res.empty()) cout << "Impossible" << endl; else { vector pre(N), suf(N); for(int i=0; i