結果
問題 | 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;}