結果
問題 | No.3031 曲面の向き付け |
ユーザー |
![]() |
提出日時 | 2025-02-21 23:14:18 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,523 bytes |
コンパイル時間 | 4,729 ms |
コンパイル使用メモリ | 304,504 KB |
実行使用メモリ | 47,824 KB |
最終ジャッジ日時 | 2025-02-21 23:14:33 |
合計ジャッジ時間 | 13,721 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 WA * 3 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;struct UnionFind {vector<int> p;UnionFind(int n):p(n,-1){}int find(int x){if(p[x] < 0) return x;return p[x] = find(p[x]);}bool unite(int x,int y) {x = find(x);y = find(y);if(x == y)return false;if(p[x] > p[y])swap(x,y);p[x] += p[y];p[y] = x;return true;}bool same(int x, int y) { return find(x) == find(y);}int size(int x) { return -p[find(x)];}};int main(){int M;cin >> M;vector<array<int, 3>> ABC(M);map<array<int, 2>, int> cnt;for (int i = 0; i < M; i++) {cin >> ABC[i][0] >> ABC[i][1] >> ABC[i][2];cnt[{ABC[i][0], ABC[i][1]}]++;cnt[{ABC[i][1], ABC[i][2]}]++;cnt[{ABC[i][0], ABC[i][2]}]++;}map<array<int, 2>, int> idx;map<int, array<int, 2>> xdi;for(auto [k, e] : cnt){if(e >= 3){cout << "NO\n";exit(0);}if(e == 2){xdi[size(idx)] = k;idx[k] = size(idx);}}int N = size(idx);vector<vector<int>> G(N);UnionFind uf(N);for (int i = 0; i < M; i++) {vector<int> to(3, -1);if(idx.contains({ABC[i][0], ABC[i][1]})){to[0] = idx[{ABC[i][0], ABC[i][1]}];}if(idx.contains({ABC[i][1], ABC[i][2]})){to[1] = idx[{ABC[i][1], ABC[i][2]}];}if(idx.contains({ABC[i][0], ABC[i][2]})){to[2] = idx[{ABC[i][0], ABC[i][2]}];}if(to[0] != -1 && to[1] != -1){uf.unite(to[0], to[1]);}if(to[1] != -1 && to[2] != -1){uf.unite(to[0], to[1]);}if(to[0] != -1 && to[2] != -1){G[to[0]].push_back(to[2]);G[to[2]].push_back(to[0]);}}vector<vector<int>> H(N);for (int i = 0; i < N; i++) {for(int j : G[i]){if(uf.same(i, j)){cout << "NO\n";exit(0);}else{H[uf.find(i)].push_back(uf.find(j));H[uf.find(j)].push_back(uf.find(i));}}}vector<int> color(N, -1);for (int i = 0; i < N; i++) {if(color[i] == -1){queue<int> q;color[i] = 1;q.push(i);while (!q.empty()) {int now = q.front();q.pop();for (int to : H[now]) {if (color[to] == -1) {color[to] = 1 - color[now];q.push(to);} else if (color[to] == color[now]) {cout << "NO\n";exit(0);}}}}}cout << "YES\n";return 0;}/*File : ~/yukicoder/528/E.cppDate : 2025/02/21Time : 22:31:48*/