제출 #204518

#제출 시각아이디문제언어결과실행 시간메모리
204518junodeveloperPotemkin cycle (CEOI15_indcyc)C++14
30 / 100
1124 ms527120 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; int cnt[1010]; bool chk[1010]; vi adj[1010]; void dfs(int u) { grp[u]=gc; for(auto& it:adj[u])if(!grp[it]&&(!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++) { mset(grp,0);gc=0; chk[i]=true; for(auto& it:adj[i])chk[it]=true; for(auto& it:adj[i])if(!grp[it]) { gc++; dfs(it); } for(j=1;j<=gc;j++)cnt[j]=0; for(auto& it:adj[i])cnt[grp[it]]++; for(auto& it:adj[i]){ int c=0; for(auto& jt:adj[it]) { if(chk[jt]&&grp[it]==grp[jt])c++; } if(c!=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...