Submission #136594

#TimeUsernameProblemLanguageResultExecution timeMemory
136594thebesPotemkin cycle (CEOI15_indcyc)C++14
30 / 100
6 ms1400 KiB
#include <bits/stdc++.h> using namespace std; const int MN = 1005, LG = 12; int n, m, i, x, y, vis[MN], d[MN], p[MN], sp[MN][LG], t[MN][2], nxt, rev[MN]; pair<int,int> e[MN]; vector<int> adj[MN], ee[MN], eee[MN], tt[MN], ans; queue<int> q; set<pair<int,int>> done; void dfs(int n,int p){ t[n][0] = ++nxt; rev[nxt] = n; sp[n][0] = p; for(auto v : tt[n]) dfs(v, n); t[n][1] = nxt; } int anc(int x,int y){ if(d[x]<d[y]) swap(x,y); for(int i=LG-1;i>=0;i--){ if((1<<i)<=d[x]-d[y]) x = sp[x][i]; } if(x==y) return x; for(int i=LG-1;i>=0;i--){ if(sp[x][i]!=sp[y][i]){ x=sp[x][i]; y=sp[y][i]; } } return sp[x][0]; } bool solve(int l,int r){ if(done.count({l,r})) return 0; done.insert({l,r}); int f=0; if(ee[l][0]<r&&solve(l,ee[l][0])) return 1; else if(ee[l][0]<r) f=1; if(eee[r].back()>l&&solve(eee[r].back(),r)) return 1; else if(eee[r].back()>l) f=1; int x = anc(rev[l], rev[r]); if(d[rev[l]]+d[rev[r]]-2*d[x]>=3&&!f){ memset(p,0,sizeof(p)); q.push(rev[l]); p[rev[l]]=-1; while(q.size()){ x = q.front(); q.pop(); for(auto v : tt[x]){ if(!p[v]){ p[v] = x; q.push(v); } } if(sp[x][0]&&!p[sp[x][0]]){ p[sp[x][0]] = x; q.push(sp[x][0]); } for(auto v : ee[t[x][0]]){ if(v==r&&x==rev[l]) continue; if(!p[rev[v]]){ p[rev[v]] = x; q.push(rev[v]); } } } x = rev[r]; while(~x){ ans.push_back(x); x = p[x]; } return 1; } } int main(){ for(scanf("%d%d",&n,&m),i=1;i<=m;i++){ scanf("%d%d",&x,&y); adj[x].push_back(y); adj[y].push_back(x); e[i]={x,y}; } q.push(1); vis[1]=1; while(q.size()){ x = q.front(); q.pop(); for(auto v : adj[x]){ if(!vis[v]){ vis[v]=1; d[v]=d[x]+1; p[v]=x; q.push(v); } } if(p[x]){ adj[p[x]].erase(find(adj[p[x]].begin(),adj[p[x]].end(),x)); adj[x].erase(find(adj[x].begin(),adj[x].end(),p[x])); } tt[p[x]].push_back(x); } dfs(1,0); for(int j=1;j<LG;j++){ for(i=1;i<=n;i++) sp[i][j]=sp[sp[i][j-1]][j-1]; } for(i=1;i<=n;i++){ for(auto v : adj[rev[i]]){ if(t[v][0]>=i) ee[i].push_back(t[v][0]); else eee[i].push_back(t[v][0]); } } for(i=1;i<=n;i++){ sort(ee[i].begin(),ee[i].end()); sort(eee[i].begin(),eee[i].end()); } for(i=1;i<=n;i++){ for(auto v : ee[i]){ if(solve(i,v)) break; } if(ans.size()) break; for(auto v : eee[i]){ if(solve(v,i)) break; } if(ans.size()) break; } if(ans.size()){ for(auto v : ans) printf("%d ",v); printf("\n"); } else printf("no\n"); return 0; }

Compilation message (stderr)

indcyc.cpp: In function 'bool solve(int, int)':
indcyc.cpp:73:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
indcyc.cpp: In function 'int main()':
indcyc.cpp:76:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%d%d",&n,&m),i=1;i<=m;i++){
         ~~~~~~~~~~~~~~~~~~~^~~~
indcyc.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
         ~~~~~^~~~~~~~~~~~~~
#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...