# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
244439 | 2020-07-04T05:56:21 Z | SomeoneUnknown | Potemkin cycle (CEOI15_indcyc) | C++14 | 25 ms | 1308 KB |
#include <bits/stdc++.h> using namespace std; int main(){ int n, r; scanf("%d %d", &n, &r); int ved[n+1]; for(int i = 1; i <= n; ++i) ved[i] = 0; //unvisited vector<int> adjlist[n+1]; for(int i = 0; i < r; ++i){ int a, b; scanf("%d %d", &a, &b); adjlist[a].push_back(b); adjlist[b].push_back(a); } for(int i = 1; i <= n; ++i){ if(ved[i] != 0) continue; ved[i] = -1; //root queue<int> tovisit; tovisit.push(i); while(!tovisit.empty()){ int ving = tovisit.front(); //printf("ving = %d\n", ving); tovisit.pop(); for(int j = 0; j < adjlist[ving].size(); ++j){ int nghbr = adjlist[ving][j]; if(ved[nghbr] == 0){ ved[nghbr] = ving; tovisit.push(nghbr); }else if(ved[ving] != nghbr && ved[ving] != ved[nghbr]){ stack<int> s; queue<int> e; //s.push(ving); //e.push(nghbr); int last; int sptr = ving; int eptr = nghbr; while(sptr != eptr){ e.push(eptr); //printf("e: %d\n", eptr); last = eptr; eptr = ved[eptr]; if(sptr == eptr) break; s.push(sptr); //printf("s: %d\n", sptr); sptr = ved[sptr]; } //return 5; //doesnt reach bool djoint = true; for(int k = 0; k < adjlist[s.top()].size(); k++){ if(adjlist[s.top()][k] == last) djoint = false; } if(djoint) printf("%d ", sptr); while(!s.empty()){ printf("%d ", s.top()); s.pop(); } while(!e.empty()){ printf("%d ", e.front()); e.pop(); } return 0; } } } } printf("no"); } /* 5 5 1 2 2 3 2 4 3 5 4 5 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 256 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 256 KB | Output is correct |
4 | Correct | 5 ms | 256 KB | Output is correct |
5 | Correct | 5 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Too short sequence |
2 | Incorrect | 5 ms | 384 KB | Wrong answer on graph without induced cycle |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Too short sequence |
2 | Incorrect | 5 ms | 384 KB | Wrong answer on graph without induced cycle |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 432 KB | Wrong answer on graph without induced cycle |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 384 KB | Too short sequence |
2 | Incorrect | 5 ms | 384 KB | Wrong answer on graph without induced cycle |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 896 KB | Too short sequence |
2 | Correct | 10 ms | 768 KB | Too short sequence |
3 | Incorrect | 16 ms | 1280 KB | Wrong answer on graph without induced cycle |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 640 KB | Too short sequence |
2 | Incorrect | 9 ms | 768 KB | Wrong answer on graph without induced cycle |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 25 ms | 1308 KB | Expected integer, but "no" found |
2 | Halted | 0 ms | 0 KB | - |