# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
244605 | 2020-07-04T11:56:47 Z | tqbfjotld | Potemkin cycle (CEOI15_indcyc) | C++14 | 951 ms | 3072 KB |
#include <bits/stdc++.h> using namespace std; int n,e; vector<int> adjl[1005]; vector<int> cur; int curpos[1005]; bool visited[1005][1005]; bool adjm[1005][1005]; int dfs(int node, int parent, int p2){ if (visited[node][parent]) return -1; //printf("node %d, %d\n",node+1,curpos[node]); if (adjm[node][p2]) return -1; int k= -1; visited[node][parent] = true; for (auto x : adjl[node]){ if (x==parent) continue; k = max(k,curpos[x]); } //printf("k: %d\n",k); if (k!=-1){ cur.push_back(node); return k; } else{ for (auto x : adjl[node]){ if (x==parent) continue; curpos[x] = curpos[node]+1; //printf("set %d\n",1+x); int res = dfs(x,node,parent); //printf("received %d\n",res); if (res>0){ cur.push_back(node); return res==curpos[node]?-2:res; } if (res==-2) return -2; curpos[x] = -1; //printf("reset %d\n",1+x); } return -1; } } int main(){ scanf("%d%d",&n,&e); memset(curpos,-1,sizeof(curpos)); for (int x = 0; x<e; x++){ int a,b; scanf("%d%d",&a,&b); a--;b--; adjl[a].push_back(b); adjl[b].push_back(a); adjm[a][b] = true; adjm[b][a] = true; } for (int x = 0; x<n; x++){ for (int y = 0; y<n; y++){ if (!adjm[x][y]) continue; if(visited[x][y]) continue; curpos[x] = 1; if (dfs(x,y,-1)==-2){ for (auto k : cur){ printf("%d ",k+1); } return 0; } curpos[x] = -1; } } printf("no"); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
3 | Correct | 4 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 | 4 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 512 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 512 KB | Output is correct |
2 | Correct | 5 ms | 512 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 1024 KB | Output is correct |
2 | Correct | 6 ms | 1024 KB | Output is correct |
3 | Correct | 7 ms | 1024 KB | Output is correct |
4 | Correct | 13 ms | 1024 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 1024 KB | Output is correct |
2 | Correct | 9 ms | 1024 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 38 ms | 2808 KB | Output is correct |
2 | Correct | 14 ms | 2688 KB | Output is correct |
3 | Correct | 100 ms | 2816 KB | Output is correct |
4 | Correct | 27 ms | 2560 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 2560 KB | Output is correct |
2 | Correct | 84 ms | 2680 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 86 ms | 1792 KB | Output is correct |
2 | Correct | 951 ms | 2436 KB | Output is correct |
3 | Correct | 24 ms | 3072 KB | Output is correct |
4 | Correct | 291 ms | 3072 KB | Output is correct |