結果
問題 | No.1023 Cyclic Tour |
ユーザー |
![]() |
提出日時 | 2020-04-10 23:05:55 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 304 ms / 2,000 ms |
コード長 | 2,027 bytes |
コンパイル時間 | 1,177 ms |
コンパイル使用メモリ | 79,864 KB |
実行使用メモリ | 27,716 KB |
最終ジャッジ日時 | 2024-09-15 23:45:40 |
合計ジャッジ時間 | 14,925 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 49 |
ソースコード
#include<iostream> #include<cstdio> #include<algorithm> #include<cassert> #include<cmath> #include<vector> #include<map> #include<set> #include<string> #include<queue> #include<stack> using namespace std; #define MOD 1000000007 #define MOD2 998244353 #define INF ((1<<30)-1) #define LINF (1LL<<60) #define EPS (1e-10) typedef long long Int; typedef pair<Int, Int> P; int n, m; vector<P> edge[110000]; vector<int> rev[110000]; vector<int> group[110000]; int a, b, c; bool done[110000]; Int comp[110000]; vector<int> nodes; void dfs(int x, int last = -1){ if(done[x])return; done[x] = true; for(auto p:edge[x]){ int to = p.first; if(to == last)continue; dfs(to, x); } nodes.push_back(x); } void dfs2(int x, int g, int last = -1){ if(done[x])return; done[x] = true; group[g].push_back(x); comp[x] = g; for(auto to:rev[x]){ if(to == last)continue; dfs2(to, g, x); } } void scc(){ for(int i = 1;i <= n;i++){ dfs(i); } reverse(nodes.begin(), nodes.end()); fill(done, done + n + 1, false); for(auto node:nodes){ if(!done[node]) dfs2(node, node); } } void ok(){ cout << "Yes" << endl; exit(0); } void ng(){ cout << "No" << endl; exit(0); } bool check(int g){ int V = group[g].size(); if(V == 0)return false; int E = 0; for(auto v:group[g]){ for(auto p:edge[v]){ if(p.second == -1)continue; int to = p.first; if(comp[to] == g)E++; } } // cout << g << " " << V << " " << E << endl; if(E+1 == V)return false; return true; } int main(){ cin >> n >> m; for(int i = 0;i < m;i++){ cin >> a >> b >> c; edge[a].push_back(P(b,c)); rev[b].push_back(a); if(c==1){ edge[b].push_back(P(a,-1)); rev[a].push_back(b); } } scc(); for(int i = 1;i <= n;i++){ if(check(i))ok(); } ng(); return 0; }