# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
31542 | 2017-08-29T08:00:31 Z | ngkan146 | Senior Postmen (BOI14_postmen) | C++ | 5 ms | 384 KB |
#include <bits/stdc++.h> using namespace std; int ctrl[500005]; int nxt[500005], prv[500005], id[1000005]; int head[500005], en[500005]; bool visited[1000005]; int n,m; int euler[1000005], eulersize; int q[1000005], qsize; void dfs(){ q[qsize++] = 1; while(qsize){ int u = q[qsize-1]; bool mjk = 0; for(;ctrl[u];ctrl[u] = nxt[ctrl[u]]){ int v = (u ^ head[id[ctrl[u]]] ^ en[id[ctrl[u]]]); //cout << "v " << v << ' ' << ctrl[u] << ' ' << head[ctrl[u]] << ' ' << en[ctrl[u]] << endl; if (visited[id[ctrl[u]]]) continue; mjk = 1; visited[id[ctrl[u]]] = 1; q[qsize++] = v; break; } if(mjk) continue; euler[eulersize++] = u; --qsize; } } int st[1000005], stsize; bool used[1000005]; int main(){ scanf("%d %d",&n,&m); int cnt = 0; for(int i=1;i<=m;++i){ int x,y; scanf("%d %d",&x,&y); nxt[prv[x]] = ++cnt, id[cnt] = i; nxt[prv[y]] = ++cnt, id[cnt] = i; if (!ctrl[x]) ctrl[x] = nxt[prv[x]]; if (!ctrl[y]) ctrl[y] = nxt[prv[y]]; prv[x] = nxt[prv[x]]; prv[y] = nxt[prv[y]]; head[i] = x; en[i] = y; } dfs(); for(int i=0;i<eulersize;++i){ if (used[euler[i]]){ while(st[stsize-1] != euler[i]){ printf("%d ",st[stsize-1]); used[st[stsize-1]] = 0; --stsize; }; printf("%d\n",euler[i]); } else{ st[stsize++] = euler[i]; used[euler[i]] = 1; } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 360 KB | Output is correct |
2 | Incorrect | 5 ms | 384 KB | Edge does not exist or used 1, 7 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Incorrect | 5 ms | 384 KB | Edge does not exist or used 1, 7 |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Incorrect | 5 ms | 384 KB | Edge does not exist or used 1, 7 |
3 | Halted | 0 ms | 0 KB | - |