# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
231119 | 2020-05-12T19:34:09 Z | MKopchev | Potemkin cycle (CEOI15_indcyc) | C++14 | 1000 ms | 2688 KB |
#include<bits/stdc++.h> using namespace std; const int nmax=1e3+42,mmax=1e5+42; int n,m; bool in[nmax][nmax]; vector<int> adj[nmax]; pair<int,int> inp[mmax]; int when[nmax],parent[nmax]; queue< pair<int/*node*/,int/*dist*/> > q,idle; void test_build(int u,int v) { q=idle; for(int i=1;i<=n;i++)when[i]=n+1; for(int i=1;i<=n;i++) if(in[i][u]&&in[i][v])when[i]=-1; q.push({u,0}); when[u]=0; while(q.size()) { pair<int/*node*/,int/*dist*/> tp=q.front(); q.pop(); for(auto k:adj[tp.first]) { if(tp.first==u&&k==v)continue; if(when[k]>when[tp.first]+1) { when[k]=when[tp.first]+1; q.push({k,when[k]}); parent[k]=tp.first; } } } /* cout<<u<<" "<<v<<endl; for(int i=1;i<=n;i++)cout<<when[i]<<" ";cout<<endl; */ if(when[v]>n)return; printf("%i",v); while(v!=u) { v=parent[v]; printf(" %i",v); } printf("\n"); exit(0); } int main() { double t=clock(); scanf("%i%i",&n,&m); for(int i=1;i<=m;i++) { int u,v; scanf("%i%i",&u,&v); in[u][v]=1; in[v][u]=1; inp[i]={u,v}; adj[u].push_back(v); adj[v].push_back(u); } for(int i=1;i<=m&&1.0*(t-clock())/CLOCKS_PER_SEC<0.9;i++) test_build(inp[i].first,inp[i].second); printf("no\n"); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 4 ms | 384 KB | Output is correct |
5 | Correct | 5 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 512 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 512 KB | Output is correct |
2 | Correct | 9 ms | 512 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 32 ms | 780 KB | Output is correct |
2 | Correct | 5 ms | 768 KB | Output is correct |
3 | Correct | 6 ms | 768 KB | Output is correct |
4 | Correct | 58 ms | 768 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 768 KB | Output is correct |
2 | Correct | 49 ms | 768 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 23 ms | 2304 KB | Output is correct |
2 | Correct | 35 ms | 1792 KB | Output is correct |
3 | Execution timed out | 1094 ms | 2304 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 147 ms | 1792 KB | Output is correct |
2 | Execution timed out | 1091 ms | 1920 KB | Time limit exceeded |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 56 ms | 2552 KB | Output is correct |
2 | Correct | 202 ms | 2560 KB | Output is correct |
3 | Correct | 73 ms | 2680 KB | Output is correct |
4 | Execution timed out | 1086 ms | 2688 KB | Time limit exceeded |