結果
問題 | No.1023 Cyclic Tour |
ユーザー | mugen_1337 |
提出日時 | 2020-05-26 22:40:16 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 406 ms / 2,000 ms |
コード長 | 3,315 bytes |
コンパイル時間 | 2,606 ms |
コンパイル使用メモリ | 221,004 KB |
実行使用メモリ | 40,700 KB |
最終ジャッジ日時 | 2023-08-03 05:24:40 |
合計ジャッジ時間 | 15,716 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,384 KB |
testcase_01 | AC | 2 ms
4,384 KB |
testcase_02 | AC | 1 ms
4,384 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 27 ms
4,380 KB |
testcase_05 | AC | 26 ms
4,380 KB |
testcase_06 | AC | 27 ms
4,384 KB |
testcase_07 | AC | 26 ms
4,380 KB |
testcase_08 | AC | 131 ms
12,532 KB |
testcase_09 | AC | 173 ms
27,452 KB |
testcase_10 | AC | 171 ms
27,712 KB |
testcase_11 | AC | 193 ms
29,124 KB |
testcase_12 | AC | 244 ms
32,116 KB |
testcase_13 | AC | 211 ms
30,296 KB |
testcase_14 | AC | 211 ms
30,124 KB |
testcase_15 | AC | 216 ms
30,640 KB |
testcase_16 | AC | 381 ms
33,520 KB |
testcase_17 | AC | 406 ms
33,896 KB |
testcase_18 | AC | 404 ms
31,224 KB |
testcase_19 | AC | 360 ms
31,260 KB |
testcase_20 | AC | 185 ms
24,060 KB |
testcase_21 | AC | 187 ms
24,660 KB |
testcase_22 | AC | 248 ms
26,980 KB |
testcase_23 | AC | 263 ms
27,556 KB |
testcase_24 | AC | 369 ms
32,644 KB |
testcase_25 | AC | 187 ms
24,008 KB |
testcase_26 | AC | 188 ms
24,052 KB |
testcase_27 | AC | 174 ms
23,044 KB |
testcase_28 | AC | 334 ms
31,376 KB |
testcase_29 | AC | 367 ms
33,092 KB |
testcase_30 | AC | 345 ms
31,660 KB |
testcase_31 | AC | 296 ms
30,404 KB |
testcase_32 | AC | 326 ms
30,884 KB |
testcase_33 | AC | 323 ms
30,944 KB |
testcase_34 | AC | 22 ms
4,400 KB |
testcase_35 | AC | 45 ms
5,084 KB |
testcase_36 | AC | 217 ms
25,200 KB |
testcase_37 | AC | 281 ms
29,112 KB |
testcase_38 | AC | 345 ms
31,512 KB |
testcase_39 | AC | 292 ms
28,060 KB |
testcase_40 | AC | 289 ms
28,524 KB |
testcase_41 | AC | 306 ms
28,360 KB |
testcase_42 | AC | 128 ms
11,780 KB |
testcase_43 | AC | 162 ms
12,996 KB |
testcase_44 | AC | 63 ms
21,228 KB |
testcase_45 | AC | 248 ms
40,700 KB |
testcase_46 | AC | 235 ms
35,708 KB |
testcase_47 | AC | 61 ms
21,580 KB |
testcase_48 | AC | 157 ms
24,940 KB |
testcase_49 | AC | 155 ms
24,868 KB |
testcase_50 | AC | 148 ms
25,116 KB |
testcase_51 | AC | 82 ms
11,804 KB |
testcase_52 | AC | 114 ms
12,020 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; #define ALL(x) x.begin(),x.end() #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define INF 1000000000 #define mod 1000000007 using ll=long long; const ll LINF=1001002003004005006ll; int dx[]={1,0,-1,0}; int dy[]={0,1,0,-1}; // ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} struct UnionFind{ vector<int> par; vector<int> siz; int c;//親の個数(グループ数) void init(int n){ c=n; for(int i=0;i<n;i++){ par.push_back(i); siz.push_back(1); } } UnionFind(int n){ init(n); } int root(int x){ //根を返す return(par[x]==x?x:(par[x]=root(par[x]))); } bool sameParent(int x,int y){ return(root(x)==root(y)); } void unite(int x, int y){ x=root(x);y=root(y); if(x==y) return; if(siz[x]<siz[y]) swap(x,y); siz[x] += siz[y];par[y]=x;c--; } int size(int x){ return siz[root(x)]; } }; struct StronglyConnectedComponents{ vector<vector<int>> g; vector<vector<int>> to,from; vector<int> comp,order,used; StronglyConnectedComponents(vector<vector<int>> &g): g(g),to(g.size()),from(g.size()),comp(g.size(),-1),used(g.size()){ for(int i=0;i<g.size();i++){ for(auto x:g[i]){ to[i].push_back(x); from[x].push_back(i); } } } int operator[](int k){ return comp[k]; } void dfs(int now){ if(used[now]) return ; used[now]=true; for(int x:to[now])dfs(x); order.push_back(now); } void rdfs(int now,int cnt){ if(comp[now]!=-1) return ; comp[now]=cnt; for(int x:from[now]) rdfs(x,cnt); } void build(vector<vector<int>> &t){ for(int i=0;i<to.size();i++) dfs(i); reverse(order.begin(),order.end()); int ptr=0; for(int i:order)if(comp[i]==-1)rdfs(i,ptr),ptr++; t.resize(ptr); for(int i=0;i<g.size();i++){ for(auto v:to[i]){ int x=comp[i],y=comp[v]; if(x==y) continue; t[x].push_back(y); } } } }; signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n,m;cin>>n>>m; UnionFind uf(n); vector<pair<int,int>> es; rep(i,m){ int a,b,c;cin>>a>>b>>c;a--,b--; if(c==1){ if(uf.sameParent(a,b)){ cout<<"Yes"<<endl; return 0; } uf.unite(a,b); } else{ es.push_back({a,b}); } } map<int,int> id; rep(i,n){ id[i]=uf.root(i); } vector<vector<int>> g(id.size()); for(auto &p:es){ if(id[p.first]==id[p.second]){ cout<<"Yes"<<endl; return 0; } g[id[p.first]].push_back(id[p.second]); } StronglyConnectedComponents SCC(g); vector<vector<int>> t; SCC.build(t); cout<<(t.size()==id.size()?"No":"Yes")<<endl; return 0; }