結果
問題 | No.1023 Cyclic Tour |
ユーザー |
![]() |
提出日時 | 2020-04-10 22:04:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 83 ms / 2,000 ms |
コード長 | 1,435 bytes |
コンパイル時間 | 1,872 ms |
コンパイル使用メモリ | 177,160 KB |
実行使用メモリ | 15,060 KB |
最終ジャッジ日時 | 2024-09-15 20:25:00 |
合計ジャッジ時間 | 7,399 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 49 |
ソースコード
#include <bits/stdc++.h> int ri() { int n; scanf("%d", &n); return n; } struct UnionFind { std::vector<int> data; UnionFind (int size) : data(size, -1) {} bool unite(int x, int y) { x = root(x); y = root(y); if (x != y) { if (data[y] < data[x]) std::swap(x, y); data[x] += data[y]; data[y] = x; } return x != y; } bool same(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } bool connected() { return size(0) == (int) data.size(); } }; std::vector<int> visited; std::vector<std::vector<int> > hen; bool dfs(int i) { visited[i] = 1; for (auto j : hen[i]) { if (visited[j] == 1) return true; if (visited[j] == 0 && dfs(j)) return true; } visited[i] = 2; return false; } bool solve() { int n = ri(); int m = ri(); UnionFind uni(n); std::vector<std::pair<int, int> > directed; for (int i = 0; i < m; i++) { int a = ri() - 1; int b = ri() - 1; int c = ri(); if (c == 1 && !uni.unite(a, b)) return true; if (c == 2) directed.push_back({a, b}); } for (auto &i : directed) i.first = uni.root(i.first), i.second = uni.root(i.second); hen.resize(n); for (auto i : directed) hen[i.first].push_back(i.second); visited.assign(n, 0); for (int i = 0; i < n; i++) if (!visited[i] && dfs(i)) return true; return false; } int main() { puts(solve() ? "Yes" : "No"); return 0; }