제출 #204519

#제출 시각아이디문제언어결과실행 시간메모리
204519junodeveloperPotemkin cycle (CEOI15_indcyc)C++14
30 / 100
1133 ms527504 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define sz(x) ((int)x.size()) #define all(x) (x).begin(), (x).end() #define pb push_back #define fi first #define se second #define mset(x,y) memset(x,y,sizeof(x)) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repr(i,a,b) for(int i=(a);i>=(b);i--) #ifdef LOCAL #define debug(...) printf(__VA_ARGS__) #else #define debug(...) 1 #endif using namespace __gnu_pbds; using namespace std; using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef vector<int> vi; int n,m; int grp[1010],gc,ver[1010],vc; int cnt[1010]; bool chk[1010]; vi adj[1010]; void dfs(int u) { grp[u]=gc; ver[u]=vc; for(auto& it:adj[u])if(ver[it]!=vc&&(!chk[u]||!chk[it]))dfs(it); } void go(int a,int b) { vector<int> d(n+1,-1),par(n+1); queue<int> q; d[b]=0;q.push(b); while(!q.empty()) { int u=q.front();q.pop(); if(chk[u]&&u!=b)continue; for(auto& it:adj[u]) { if(d[it]!=-1||(chk[u]&&chk[it]))continue; d[it]=d[u]+1; par[it]=u; q.push(it); } } for(auto& it:adj[b]) { if(!chk[it])continue; d[it]=0; } int e=-1; for(auto& it:adj[a]) if(d[it]>0) e=it; vi ans; while(e!=b)ans.pb(e),e=par[e]; ans.pb(b);ans.pb(a); for(auto& it:ans)printf("%d ",it); } namespace FIO { using ll=long long; int _curr, _size; char _buff[1<<25]; char rc() { if(_curr == _size) { _size = (int)fread(_buff, 1, sizeof(_buff), stdin); _curr = 0; } if(!_size) return 0; return _buff[_curr++]; } ll ri() { ll c, x = 0, f = 1; while((c = rc()) <= 32); if(c == '-') f = -1, c = rc(); while(c > 32) x = (x << 3) + (x << 1) + c - 48, c = rc(); return x * f; } } using namespace FIO; int main() { int i,j; //scanf("%d%d",&n,&m); n=ri(),m=ri(); for(i=1;i<=m;i++) { int u=ri(),v=ri(); //scanf("%d%d",&u,&v); adj[u].pb(v); adj[v].pb(u); } for(i=1;i<=n;i++) { chk[i]=true;vc=i; for(auto& it:adj[i])chk[it]=true; for(auto& it:adj[i])if(ver[it]!=vc) { gc++; dfs(it); cnt[gc]=0; } for(auto& it:adj[i])cnt[grp[it]]++; for(auto& it:adj[i]){ j=0; for(auto& jt:adj[it]) { if(chk[jt]&&grp[it]==grp[jt])j++; } if(j!=cnt[grp[it]]-1) { go(i,it); return 0; } } chk[i]=false; for(auto& it:adj[i])chk[it]=false; } puts("no"); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...