結果
問題 | No.274 The Wall |
ユーザー |
![]() |
提出日時 | 2019-10-03 15:32:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 459 ms / 2,000 ms |
コード長 | 2,724 bytes |
コンパイル時間 | 1,933 ms |
コンパイル使用メモリ | 181,660 KB |
実行使用メモリ | 132,608 KB |
最終ジャッジ日時 | 2024-06-22 02:32:40 |
合計ジャッジ時間 | 4,176 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h>using namespace std;struct StronglyConnectedComponent {const int V;vector<vector<int>> G, revG;vector<int> id;StronglyConnectedComponent(const int V) :V(V),G(vector<vector<int>>(V, vector<int>())),revG(vector<vector<int>>(V, vector<int>())),id(vector<int>(V)){}void addEdge(int from, int to) {G[from].push_back(to);revG[to].push_back(from);}void build() {vector<bool> used(V, false);stack<int> st;for(int from = 0; from < V; ++from) {if(not used[from]) {dfs(from, used, st);}}int num = 0;while(st.size()) {int from = st.top();st.pop();if(used[from]) {revdfs(from, num, used);++num;}}}void dfs(int from, vector<bool> &used, stack<int> &st) {used[from] = true;for(int to : G[from]) {if(not used[to]) {dfs(to, used, st);}}st.push(from);}void revdfs(int from, int num, vector<bool> &used) {used[from] = false;id[from] = num;for(int to : revG[from]) {if(used[to]) {revdfs(to, num, used);}}}int get(int x) {return id[x];}};struct TwoSatisfiability {const int V;vector<vector<int>> G;vector<bool> pos;StronglyConnectedComponent scc;TwoSatisfiability(const int V) :V(V),G(vector<vector<int>>(2 * V, vector<int>())),pos(vector<bool>(2 * V)),scc(StronglyConnectedComponent(2 * V)){}// a or bvoid addEdge(int a, bool apos, int b, bool bpos) {if(not apos) a += V;if(not bpos) b += V;scc.addEdge((a + V) % (2 * V), b); // not a -> bscc.addEdge((b + V) % (2 * V), a); // not b -> a}bool solve() {scc.build();for(int i = 0; i < V; ++i) {if(scc.get(i) == scc.get(i + V)) {return false;}pos[i] = (scc.get(i) > scc.get(i + V));}return true;}bool get(int x) {return pos[x];}};int main() {int n, m; cin >> n >> m;TwoSatisfiability sat(n);int l[n], r[n];for(int i = 0; i < n; ++i) {cin >> l[i] >> r[i];}for(int i = 0; i < n; ++i) {for(int j = i + 1; j < n; ++j) {for(int mask = 0; mask < (1 << 2); ++mask) {bool ipos = (mask & 1);bool jpos = ((mask >> 1) & 1);int li = l[i], ri = r[i];if(not ipos) {li = (m - 1) - li;ri = (m - 1) - ri;swap(li, ri);}int lj = l[j], rj = r[j];if(not jpos) {lj = (m - 1) - lj;rj = (m - 1) - rj;swap(lj, rj);}// 衝突するとき// not (A and B)// => (not A) or (not B)if(li <= lj) {if(lj <= ri) {sat.addEdge(i, not ipos, j, not jpos);}} else {if(li <= rj) {sat.addEdge(i, not ipos, j, not jpos);}}}}}cout << (sat.solve() ? "YES" : "NO") << '\n';return 0;}