# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
31548 | 2017-08-29T08:09:23 Z | ngkan146 | Senior Postmen (BOI14_postmen) | C++ | 487 ms | 26232 KB |
#include <bits/stdc++.h> using namespace std; int ctrl[500005]; int nxt[1000005], prv[1000005], id[1000005]; int head[500005], en[500005]; bool visited[500005]; 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]]]); 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); if (!ctrl[x]){ ctrl[x] = ++cnt; id[cnt] = i; prv[x] = cnt; } else nxt[prv[x]] = ++cnt, id[cnt] = i, prv[x] = cnt; if (!ctrl[y]){ ctrl[y] = ++cnt; id[cnt] = i; prv[y] = cnt; } else nxt[prv[y]] = ++cnt, id[cnt] = i, prv[y] = cnt; 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 | 384 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 6 ms | 512 KB | Output is correct |
5 | Correct | 5 ms | 384 KB | Output is correct |
6 | Correct | 6 ms | 512 KB | Output is correct |
7 | Correct | 10 ms | 1024 KB | Output is correct |
8 | Correct | 5 ms | 512 KB | Output is correct |
9 | Correct | 40 ms | 4068 KB | Output is correct |
10 | Correct | 8 ms | 512 KB | Output is correct |
11 | Correct | 6 ms | 512 KB | Output is correct |
12 | Correct | 56 ms | 4088 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 384 KB | Output is correct |
2 | Correct | 6 ms | 384 KB | Output is correct |
3 | Correct | 6 ms | 384 KB | Output is correct |
4 | Correct | 7 ms | 488 KB | Output is correct |
5 | Correct | 5 ms | 384 KB | Output is correct |
6 | Correct | 7 ms | 512 KB | Output is correct |
7 | Correct | 10 ms | 1024 KB | Output is correct |
8 | Correct | 6 ms | 512 KB | Output is correct |
9 | Correct | 41 ms | 4088 KB | Output is correct |
10 | Correct | 7 ms | 512 KB | Output is correct |
11 | Correct | 6 ms | 512 KB | Output is correct |
12 | Correct | 48 ms | 4088 KB | Output is correct |
13 | Correct | 55 ms | 5624 KB | Output is correct |
14 | Correct | 70 ms | 4960 KB | Output is correct |
15 | Correct | 60 ms | 4704 KB | Output is correct |
16 | Correct | 53 ms | 5496 KB | Output is correct |
17 | Correct | 70 ms | 4452 KB | Output is correct |
18 | Correct | 61 ms | 4900 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 6 ms | 512 KB | Output is correct |
5 | Correct | 5 ms | 512 KB | Output is correct |
6 | Correct | 8 ms | 640 KB | Output is correct |
7 | Correct | 16 ms | 896 KB | Output is correct |
8 | Correct | 6 ms | 512 KB | Output is correct |
9 | Correct | 42 ms | 3960 KB | Output is correct |
10 | Correct | 6 ms | 512 KB | Output is correct |
11 | Correct | 5 ms | 512 KB | Output is correct |
12 | Correct | 45 ms | 4096 KB | Output is correct |
13 | Correct | 52 ms | 5496 KB | Output is correct |
14 | Correct | 54 ms | 4856 KB | Output is correct |
15 | Correct | 55 ms | 4728 KB | Output is correct |
16 | Correct | 74 ms | 5496 KB | Output is correct |
17 | Correct | 56 ms | 4520 KB | Output is correct |
18 | Correct | 55 ms | 4856 KB | Output is correct |
19 | Correct | 428 ms | 26208 KB | Output is correct |
20 | Correct | 451 ms | 23160 KB | Output is correct |
21 | Correct | 370 ms | 22064 KB | Output is correct |
22 | Correct | 455 ms | 26232 KB | Output is correct |
23 | Correct | 187 ms | 18552 KB | Output is correct |
24 | Correct | 487 ms | 20796 KB | Output is correct |
25 | Correct | 473 ms | 23104 KB | Output is correct |