結果
問題 | No.3031 曲面の向き付け |
ユーザー |
|
提出日時 | 2025-02-21 23:09:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,235 bytes |
コンパイル時間 | 1,353 ms |
コンパイル使用メモリ | 91,452 KB |
実行使用メモリ | 38,020 KB |
最終ジャッジ日時 | 2025-02-21 23:09:29 |
合計ジャッジ時間 | 7,202 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 WA * 1 |
other | AC * 27 WA * 2 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:66:22: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 66 | for (const auto& [e, tris] : edgeMap) { | ^ main.cpp:75:22: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 75 | for (const auto& [e, tris] : edgeMap) { | ^
ソースコード
#include <iostream>#include <vector>#include <unordered_map>#include <queue>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>()( ((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);}// 检查是否有边被超过2个三角形共享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;}