結果
問題 | No.3031 曲面の向き付け |
ユーザー |
|
提出日時 | 2025-02-21 23:30:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,441 bytes |
コンパイル時間 | 1,181 ms |
コンパイル使用メモリ | 85,840 KB |
実行使用メモリ | 36,484 KB |
最終ジャッジ日時 | 2025-02-21 23:30:46 |
合計ジャッジ時間 | 6,625 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 WA * 1 |
other | AC * 24 WA * 5 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:81:22: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 81 | for (const auto& [e, tris] : edgeMap) { | ^ main.cpp:91:22: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 91 | for (const auto& [e, tris] : edgeMap) { | ^
ソースコード
#include <iostream>#include <vector>#include <unordered_map>#include <tuple>using namespace std;struct Edge {int u, v;Edge(int a, int b) : u(min(a, b)), v(max(a, b)) {}bool operator==(const Edge& other) const {return u == other.u && v == other.v;}};namespace std {template<> struct hash<Edge> {size_t operator()(const Edge& e) const {return hash<long long>()( (static_cast<long long>(e.u) << 32) ^ e.v );}};}struct UnionFind {vector<int> parent;vector<int> rank;vector<int> weight; // 权重表示相对方向UnionFind(int n) : parent(n), rank(n, 0), weight(n, 0) {for (int i = 0; i < n; ++i) parent[i] = i;}int find(int x) {if (parent[x] != x) {int root = find(parent[x]);weight[x] ^= weight[parent[x]];parent[x] = root;}return parent[x];}bool unite(int x, int y, int w) {int px = find(x);int py = find(y);if (px == py) {return (weight[x] ^ weight[y]) == w;}if (rank[px] < rank[py]) {swap(px, py);swap(x, y);w ^= 1; // 方向交换需要翻转权重}parent[py] = px;weight[py] = weight[y] ^ w ^ weight[x];if (rank[px] == rank[py]) rank[px]++;return true;}};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int M;cin >> M;unordered_map<Edge, vector<int>> edgeMap;vector<tuple<int, int, int>> triangles(M);for (int i = 0; i < M; ++i) {int a, b, c;cin >> a >> b >> c;triangles[i] = {a, b, c};edgeMap[Edge(a, b)].push_back(i);edgeMap[Edge(b, c)].push_back(i);edgeMap[Edge(a, c)].push_back(i);}for (const auto& [e, tris] : edgeMap) {if (tris.size() > 2) {cout << "NO\n";return 0;}}UnionFind uf(M);bool possible = true;for (const auto& [e, tris] : edgeMap) {if (tris.size() == 2) {int u = tris[0], v = tris[1];if (!uf.unite(u, v, 1)) { // 共享边需要方向相反possible = false;break;}}}cout << (possible ? "YES" : "NO") << endl;return 0;}