結果
問題 | No.1023 Cyclic Tour |
ユーザー |
|
提出日時 | 2020-04-15 12:38:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,197 bytes |
コンパイル時間 | 1,014 ms |
コンパイル使用メモリ | 82,012 KB |
実行使用メモリ | 11,612 KB |
最終ジャッジ日時 | 2024-10-01 18:42:35 |
合計ジャッジ時間 | 10,710 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 47 WA * 2 |
コンパイルメッセージ
main.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 37 | main() | ^~~~
ソースコード
#include<iostream>#include<vector>#include<queue>using namespace std;#include<vector>struct UF{int n;vector<int>parent,rank;UF(int n_=0):n(n_),parent(n_),rank(n_,1){for(int i=0;i<n_;i++)parent[i]=i;}int find(int a){return parent[a]!=a?parent[a]=find(parent[a]):a;}bool same(int a,int b){return find(a)==find(b);}bool unite(int a,int b){a=find(a),b=find(b);if(a==b)return false;if(rank[a]<rank[b]){parent[a]=b;rank[b]+=rank[a];}else{parent[b]=a;rank[a]+=rank[b];}return true;}int size(int a){return rank[find(a)];}};int N,M;vector<pair<int,int> >edge;vector<int>G[1<<17];int cnt[1<<17];main(){cin>>N>>M;UF uf(N);for(int i=0;i<M;i++){int a,b,c;cin>>a>>b>>c;a--,b--;if(c==1)uf.unite(a,b);else edge.push_back(make_pair(a,b));}for(pair<int,int>p:edge){int u=uf.find(p.first);int v=uf.find(p.second);G[u].push_back(v);cnt[v]++;}queue<int>P;int vc=0;for(int i=0;i<N;i++)if(uf.find(i)==i){vc++;if(cnt[i]==0)P.push(i);}int pc=0;while(!P.empty()){pc++;int u=P.front();P.pop();for(int v:G[u])if(--cnt[v]==0)P.push(v);}cout<<(vc==pc?"No":"Yes")<<endl;}