結果
問題 | No.3031 曲面の向き付け |
ユーザー |
|
提出日時 | 2025-02-21 23:08:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 567 ms / 2,000 ms |
コード長 | 2,158 bytes |
コンパイル時間 | 3,045 ms |
コンパイル使用メモリ | 212,724 KB |
実行使用メモリ | 37,632 KB |
最終ジャッジ日時 | 2025-02-21 23:08:49 |
合計ジャッジ時間 | 10,221 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
#include <bits/stdc++.h>using namespace std;void Yes(){cout << "YES\n";}void No(){cout << "NO\n";}int main(){ios_base::sync_with_stdio(false);cin.tie(nullptr);int N; cin >> N;vector<tuple<int,int,int>> ABC(N);map<pair<int,int>,vector<int>> M;int idx = 0;for(auto &[a,b,c] : ABC){cin >> a >> b >> c;M[{a,b}].push_back(idx);M[{b,c}].push_back(idx);M[{a,c}].push_back(idx++);}bool yes = true;vector<int> LR(N,-1);for(int i=0; i<N; i++){if(LR.at(i) != -1) continue;LR.at(i) = 0;queue<int> Q; Q.push(i);while(Q.size()){int pos = Q.front(); Q.pop();auto [a1,b1,c1] = ABC.at(pos);for(auto to : M[{a1,b1}]){if(to == pos) continue;auto [a2,b2,c2] = ABC.at(to);int lr = LR.at(pos);int t = 0;if(a2 == a1 && c2 == b1) t = 1;lr ^= 1^t;if(LR.at(to) == -1) LR.at(to) = lr,Q.push(to);else if(LR.at(to) != lr){yes = false; break;}}if(!yes) break;for(auto to : M[{b1,c1}]){if(to == pos) continue;auto [a2,b2,c2] = ABC.at(to);int lr = LR.at(pos);int t = 0;if(a2 == b1 && c2 == c1) t = 1;lr ^= 1^t;if(LR.at(to) == -1) LR.at(to) = lr,Q.push(to);else if(LR.at(to) != lr){yes = false; break;}}if(!yes) break;for(auto to : M[{a1,c1}]){if(to == pos) continue;auto [a2,b2,c2] = ABC.at(to);int lr = LR.at(pos);int t = 0;if(a2 == a1 && c2 == c1) t = 1;lr ^= t;if(LR.at(to) == -1) LR.at(to) = lr,Q.push(to);else if(LR.at(to) != lr){yes = false; break;}}if(!yes) break;}if(!yes) break;}if(yes) Yes();else No();}