結果
問題 | No.3031 曲面の向き付け |
ユーザー |
![]() |
提出日時 | 2025-02-21 23:25:35 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,616 bytes |
コンパイル時間 | 4,881 ms |
コンパイル使用メモリ | 309,428 KB |
実行使用メモリ | 96,188 KB |
最終ジャッジ日時 | 2025-02-21 23:25:56 |
合計ジャッジ時間 | 20,929 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 WA * 2 |
ソースコード
#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);}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){G[to[1]].push_back(to[2]);}if(to[0] != -1 && to[2] != -1){G[to[0]].push_back(to[2]);}}map<int, int> m;int tmp = 0;for (int i = 0; i < N; i++) {if(uf.find(i) == i){m[i] = tmp;tmp++;}}vector<vector<int>> H(tmp);for (int i = 0; i < N; i++) {for(int j : G[i]){if(uf.same(i, j)){cout << "NO\n";exit(0);}else{H[m[uf.find(i)]].push_back(m[uf.find(j)]);H[m[uf.find(j)]].push_back(m[uf.find(i)]);}}}vector<int> color(tmp, -1);for (int i = 0; i < tmp; 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*/