# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
11591 | 2014-12-03T00:34:54 Z | gs14004 | Senior Postmen (BOI14_postmen) | C++ | 427 ms | 25500 KB |
#include <cstdio> #include <vector> #include <stack> #include <cstring> using namespace std; int n,m; int st[1000005], back[1000005], link[1000005], v[500005], nex[1000005], sz; vector<int> cyc, temp; void add_edge(int s, int e){ sz++; link[sz] = e; back[sz] = st[s]; st[s] = sz; nex[back[sz]] = sz; sz++; link[sz] = s; back[sz] = st[e]; st[e] = sz; nex[back[sz]] = sz; } void f(int x){ stack<int> s; s.push(1); while (!s.empty()) { int x = s.top(); int p = st[x]; int pushed = 0; while (p) { int pos = link[p]; int q = (p+1)/2; int r = p; if(p&1) r++; else r--; st[x] = p = back[p]; if(r == st[pos]){ st[pos] = back[r]; } else{ int s = nex[r]; back[s] = back[r]; nex[back[r]] = s; } if(!v[q]){ v[q]=1; s.push(pos); pushed++; break; } } if(!pushed) s.pop(); if(!pushed) cyc.push_back(x); } } int vis[500005]; int main(){ scanf("%d %d",&n,&m); for (int i=0; i<m; i++) { int s,e; scanf("%d %d",&s,&e); add_edge(s,e); } f(1); for (int i=0; i<cyc.size(); i++) { temp.push_back(cyc[i]); if(vis[cyc[i]]){ printf("%d",temp.back()); temp.pop_back(); while(temp.back() != cyc[i]){ printf(" %d",temp.back()); vis[temp.back()] = 0; temp.pop_back(); if(temp.back() == cyc[i]) printf("\n"); } } else vis[cyc[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 | 488 KB | Output is correct |
5 | Correct | 5 ms | 384 KB | Output is correct |
6 | Correct | 6 ms | 560 KB | Output is correct |
7 | Correct | 10 ms | 1024 KB | Output is correct |
8 | Correct | 7 ms | 512 KB | Output is correct |
9 | Correct | 49 ms | 4212 KB | Output is correct |
10 | Correct | 6 ms | 512 KB | Output is correct |
11 | Correct | 6 ms | 512 KB | Output is correct |
12 | Correct | 51 ms | 4420 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 | 7 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 | 6 ms | 384 KB | Output is correct |
9 | Correct | 54 ms | 4312 KB | Output is correct |
10 | Correct | 8 ms | 512 KB | Output is correct |
11 | Correct | 7 ms | 512 KB | Output is correct |
12 | Correct | 68 ms | 4396 KB | Output is correct |
13 | Correct | 81 ms | 5388 KB | Output is correct |
14 | Correct | 57 ms | 5208 KB | Output is correct |
15 | Correct | 60 ms | 4904 KB | Output is correct |
16 | Correct | 55 ms | 5368 KB | Output is correct |
17 | Correct | 53 ms | 4712 KB | Output is correct |
18 | Correct | 50 ms | 5080 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 | 7 ms | 488 KB | Output is correct |
5 | Correct | 6 ms | 384 KB | Output is correct |
6 | Correct | 6 ms | 512 KB | Output is correct |
7 | Correct | 11 ms | 1024 KB | Output is correct |
8 | Correct | 5 ms | 384 KB | Output is correct |
9 | Correct | 50 ms | 4188 KB | Output is correct |
10 | Correct | 6 ms | 512 KB | Output is correct |
11 | Correct | 6 ms | 512 KB | Output is correct |
12 | Correct | 48 ms | 4348 KB | Output is correct |
13 | Correct | 60 ms | 5412 KB | Output is correct |
14 | Correct | 56 ms | 5044 KB | Output is correct |
15 | Correct | 61 ms | 4796 KB | Output is correct |
16 | Correct | 52 ms | 5412 KB | Output is correct |
17 | Correct | 56 ms | 4712 KB | Output is correct |
18 | Correct | 51 ms | 5028 KB | Output is correct |
19 | Correct | 379 ms | 25408 KB | Output is correct |
20 | Correct | 390 ms | 24384 KB | Output is correct |
21 | Correct | 338 ms | 21272 KB | Output is correct |
22 | Correct | 388 ms | 25500 KB | Output is correct |
23 | Correct | 212 ms | 18064 KB | Output is correct |
24 | Correct | 427 ms | 22096 KB | Output is correct |
25 | Correct | 370 ms | 23692 KB | Output is correct |