結果
問題 | No.3031 曲面の向き付け |
ユーザー |
|
提出日時 | 2025-02-21 23:10:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,237 bytes |
コンパイル時間 | 1,316 ms |
コンパイル使用メモリ | 91,328 KB |
実行使用メモリ | 38,020 KB |
最終ジャッジ日時 | 2025-02-21 23:10:45 |
合計ジャッジ時間 | 7,112 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 WA * 1 |
other | AC * 27 WA * 2 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:67:22: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 67 | for (const auto& [e, tris] : edgeMap) { | ^ main.cpp:76:22: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 76 | for (const auto& [e, tris] : edgeMap) { | ^
ソースコード
#include <iostream>#include <vector>#include <unordered_map>#include <queue>#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 );}};}bool isBipartite(const vector<vector<int>>& graph, int start, vector<int>& color) {queue<int> q;q.push(start);color[start] = 0;while (!q.empty()) {int u = q.front();q.pop();for (int v : graph[u]) {if (color[v] == -1) {color[v] = color[u] ^ 1;q.push(v);} else if (color[v] == color[u]) {return false;}}}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;}}// 构建约束图vector<vector<int>> graph(M);for (const auto& [e, tris] : edgeMap) {if (tris.size() == 2) {int u = tris[0], v = tris[1];graph[u].push_back(v);graph[v].push_back(u);}}// 二分图检测vector<int> color(M, -1);for (int i = 0; i < M; ++i) {if (color[i] == -1) {if (!isBipartite(graph, i, color)) {cout << "NO\n";return 0;}}}cout << "YES\n";return 0;}