# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
31547 | 2017-08-29T08:07:58 Z | ngkan146 | 어르신 집배원 (BOI14_postmen) | C++ | 475 ms | 26288 KB |
#include <bits/stdc++.h> using namespace std; int ctrl[1000005]; int nxt[1000005], prv[1000005], id[1000005]; int head[1000005], en[1000005]; 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]]]); 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
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 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 | 5 ms | 512 KB | Output is correct |
5 | Correct | 5 ms | 384 KB | Output is correct |
6 | Correct | 6 ms | 692 KB | Output is correct |
7 | Correct | 10 ms | 896 KB | Output is correct |
8 | Correct | 5 ms | 512 KB | Output is correct |
9 | Correct | 41 ms | 3960 KB | Output is correct |
10 | Correct | 8 ms | 512 KB | Output is correct |
11 | Correct | 8 ms | 512 KB | Output is correct |
12 | Correct | 52 ms | 4088 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 | 560 KB | Output is correct |
5 | Correct | 5 ms | 384 KB | Output is correct |
6 | Correct | 6 ms | 640 KB | Output is correct |
7 | Correct | 10 ms | 1000 KB | Output is correct |
8 | Correct | 6 ms | 512 KB | Output is correct |
9 | Correct | 41 ms | 4088 KB | Output is correct |
10 | Correct | 6 ms | 512 KB | Output is correct |
11 | Correct | 5 ms | 512 KB | Output is correct |
12 | Correct | 47 ms | 4072 KB | Output is correct |
13 | Correct | 54 ms | 5500 KB | Output is correct |
14 | Correct | 57 ms | 4832 KB | Output is correct |
15 | Correct | 54 ms | 4728 KB | Output is correct |
16 | Correct | 80 ms | 5600 KB | Output is correct |
17 | Correct | 57 ms | 4472 KB | Output is correct |
18 | Correct | 51 ms | 4832 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 | 1000 KB | Output is correct |
8 | Correct | 5 ms | 512 KB | Output is correct |
9 | Correct | 51 ms | 4088 KB | Output is correct |
10 | Correct | 6 ms | 512 KB | Output is correct |
11 | Correct | 6 ms | 512 KB | Output is correct |
12 | Correct | 45 ms | 4088 KB | Output is correct |
13 | Correct | 57 ms | 5624 KB | Output is correct |
14 | Correct | 54 ms | 4880 KB | Output is correct |
15 | Correct | 66 ms | 4672 KB | Output is correct |
16 | Correct | 65 ms | 5472 KB | Output is correct |
17 | Correct | 62 ms | 4472 KB | Output is correct |
18 | Correct | 55 ms | 4816 KB | Output is correct |
19 | Correct | 441 ms | 26288 KB | Output is correct |
20 | Correct | 404 ms | 23184 KB | Output is correct |
21 | Correct | 382 ms | 22068 KB | Output is correct |
22 | Correct | 434 ms | 26224 KB | Output is correct |
23 | Correct | 201 ms | 18628 KB | Output is correct |
24 | Correct | 475 ms | 20832 KB | Output is correct |
25 | Correct | 468 ms | 23088 KB | Output is correct |