# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
527326 | 2022-02-17T07:47:15 Z | jamielim | Potemkin cycle (CEOI15_indcyc) | C++14 | 228 ms | 4780 KB |
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define mp make_pair #define pb emplace_back #define ALL(x) x.begin(),x.end() #define SZ(x) (int)x.size() typedef long long ll; typedef pair<int,int> ii; typedef pair<ii,ii> i4; const int MOD=1000000007; const int INF=1012345678; const ll LLINF=1012345678012345678LL; const double PI=3.1415926536; const double EPS=1e-14; int n,r; vector<int> adj[1005]; int mat[1005][1005]; int main(){ scanf("%d%d",&n,&r); int a,b; for(int i=0;i<r;i++){ scanf("%d%d",&a,&b);a--;b--; adj[a].pb(b); adj[b].pb(a); mat[a][b]=1;mat[b][a]=1; } vector<int> ans; for(int s=0;s<n;s++){ int dist[n]; for(int i=0;i<n;i++)dist[i]=INF; dist[s]=0; int par[n];par[s]=-1; queue<int> q; q.push(s); pair<int,int> p; int d=INF; while(!q.empty()){ int cur=q.front();q.pop(); for(int i:adj[cur]){ if(dist[i]>dist[cur]+1){ dist[i]=dist[cur]+1; par[i]=cur; q.push(i); }else{ if(i!=par[cur]&&dist[i]+dist[cur]+1<d&&dist[i]+dist[cur]+1>3){ if(dist[i]+dist[cur]+1==4){ if(cur!=s&&i!=s){ if(mat[i][par[cur]]==1||mat[cur][par[i]]==1)continue; } if(i==s){ if(mat[i][par[cur]]==1||mat[i][par[par[cur]]]==1)continue; } if(cur==s){ if(mat[cur][par[i]]==1||mat[cur][par[par[i]]]==1)continue; } } d=dist[i]+dist[cur]+1; p=mp(i,cur); } } } if(par[s]!=-1)break; } if(d>=INF)continue; vector<int> v; int cur=p.fi; while(cur!=s){ v.pb(cur); cur=par[cur]; } v.pb(s); reverse(ALL(v)); cur=p.se; while(cur!=s){ v.pb(cur); cur=par[cur]; } //printf("%d %d %d %d\n",s,SZ(v),p.fi,p.se); //for(int i:v)printf("%d ",i+1); //printf("\n"); if(ans.empty()||SZ(v)<SZ(ans)){ ans.clear(); for(int i:v)ans.pb(i); } } if(ans.empty())printf("no"); else{ for(int i:ans)printf("%d ",i+1); } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Incorrect | 1 ms | 384 KB | Wrong answer on graph without induced cycle |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Incorrect | 0 ms | 332 KB | Wrong answer on graph without induced cycle |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 716 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 716 KB | Repeated vertex |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 7 ms | 1484 KB | Wrong answer on graph without induced cycle |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 11 ms | 1544 KB | Repeated vertex |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 228 ms | 4780 KB | Repeated vertex |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 198 ms | 4512 KB | Wrong adjacency |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 140 ms | 2956 KB | Repeated vertex |
2 | Halted | 0 ms | 0 KB | - |