結果
問題 | No.3031 曲面の向き付け |
ユーザー |
|
提出日時 | 2025-02-21 23:07:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,736 bytes |
コンパイル時間 | 5,363 ms |
コンパイル使用メモリ | 272,720 KB |
実行使用メモリ | 37,700 KB |
最終ジャッジ日時 | 2025-02-21 23:07:57 |
合計ジャッジ時間 | 12,933 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 WA * 13 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using ll = long long;int main(){ios::sync_with_stdio(false);cin.tie(0);int m;cin >> m;vector<tuple<int,int,int>> a(m);vector<int> ca;for(auto &&[A, B, C] : a){cin >> A >> B >> C;ca.emplace_back(A);ca.emplace_back(B);ca.emplace_back(C);}sort(ca.begin(), ca.end());ca.erase(unique(ca.begin(), ca.end()), ca.end());vector<int> cnt(ca.size());atcoder::dsu uf(m);vector<pair<ll,int>> c2;map<ll, int> mp;for(int i = 0; i < m; i++){auto &&[A, B, C] = a[i];A = lower_bound(ca.begin(), ca.end(), A) - ca.begin();B = lower_bound(ca.begin(), ca.end(), B) - ca.begin();C = lower_bound(ca.begin(), ca.end(), C) - ca.begin();cnt[A]++, cnt[B]++, cnt[C]++;c2.emplace_back(((ll)(A) << 30) + B, i);c2.emplace_back(((ll)(A) << 30) + C, i);c2.emplace_back(((ll)(B) << 30) + C, i);mp[((ll)(A) << 30) + B]++;mp[((ll)(A) << 30) + C]++;mp[((ll)(B) << 30) + C]++;}sort(c2.begin(), c2.end());for(int i = 0; i < c2.size(); ){int p = i;while(i < c2.size() && c2[i].first == c2[p].first){uf.merge(c2[p].second, c2[i++].second);}}for(auto vec : uf.groups()){auto [A, B, C] = a[vec[0]];int v = mp[((ll)(A) << 30) + B];for(auto v2 : vec){auto [A, B, C] = a[v2];if(v != mp[((ll)(A) << 30) + B] || v != mp[((ll)(A) << 30) + C] || v != mp[((ll)(B) << 30) + C]){cout << "NO\n";return 0;}}}cout << "YES\n";}