結果
問題 |
No.3031 曲面の向き付け
|
ユーザー |
|
提出日時 | 2025-02-21 23:17:19 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 655 ms / 2,000 ms |
コード長 | 1,023 bytes |
コンパイル時間 | 4,713 ms |
コンパイル使用メモリ | 266,656 KB |
実行使用メモリ | 57,116 KB |
最終ジャッジ日時 | 2025-02-21 23:17:38 |
合計ジャッジ時間 | 14,698 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; int main () { int N; cin >> N; int siz = 0; map<pair<int, int>, int> mp; std::vector<int> cnt; vector<vector<int>> ids; vector<tuple<int, int, int>> A(N); using P = pair<int, int>; for (int j = 0; j < N; j ++) { auto& [a, b, c] = A[j]; cin >> a >> b >> c; int X[] = {a, b, c, a}; for (int i = 0; i < 3; i ++) { int p = min(X[i], X[i+1]), q = max(X[i], X[i+1]); if (mp.find(P{p, q}) == mp.end()) { mp[P{p, q}] = siz++; cnt.push_back(0); ids.push_back({}); } cnt[mp[P{p, q}]] ++; ids[mp[P{p, q}]].push_back((j + 1) * (i < 2 ? 1 : -1)); } } if (*max_element(cnt.begin(), cnt.end()) > 2) { puts("NO"); return 0; } two_sat TS(siz); for (auto& v : ids) { if (v.size() == 2) { int a = v[0], b = v[1]; int i = abs(a), j = abs(b); TS.add_clause(i, (a > 0), j, (b > 0)); TS.add_clause(i, (a < 0), j, (b < 0)); } } cout << (TS.satisfiable() ? "YES" : "NO") << endl; }