# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
5962 | 2014-06-07T05:23:11 Z | model_code | Senior Postmen (BOI14_postmen) | C++ | 439 ms | 25380 KB |
#include <cstdio> #include <set> #include <vector> #include <algorithm> using namespace std; const int MaxN = 500010, MaxM = 2*500010; int E[MaxM][3]; int pr[MaxN] = {0}; int P[MaxN], tmp[MaxN] = {0}, C[MaxN]; int k[MaxM]; int N, M, a, b; bool visited[MaxN] = {0}; vector<int> path; int newv = -1, u; int getU (int i, int v) { return (v == E[i][0]) ? E[i][1] : E[i][0]; } void dfs(int v) { path.clear(); path.push_back(v); while (v != -1) { //printf("V = %d!!!\n", v); visited[v] = true; newv = -1; for (; pr[v] < C[v]; pr[v]++) { int i = k[P[v] + pr[v]]; if (E[i][2] == false) { u = getU(i, v); E[i][2] = true; if (visited[u]) { newv = u; while (path.back() != u) { printf("%d ", path.back()); visited[path.back()] = false; path.pop_back(); } printf("%d\n", path.back()); }else { newv = u; path.push_back(u); } break; } } if (newv == -1 and path.size() > 1) { newv = path.back(); path.pop_back(); } v =newv; } visited[path[0]] = false; //for (int i = 0; i < path.size(); i++) // visited[path[i]] = false; } int main() { path.reserve(MaxN); scanf("%d%d\n", &N, &M); for (int i = 0; i < M; i++) { scanf("%d%d", &E[i][0], &E[i][1]); C[E[i][0]]++; C[E[i][1]]++; } P[1] = 0; for (int i = 2; i <= N; i++) { P[i] = P[i-1] + C[i-1]; } for (int i = 0; i < M; i++) { a = E[i][0]; b = E[i][1]; k[P[a] + tmp[a]] = i; k[P[b] + tmp[b]] = i; tmp[a]++; tmp[b]++; } for (int i = 1; i <= N; i++) { dfs(i); } return 0; }
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 | 472 KB | Output is correct |
5 | Correct | 5 ms | 384 KB | Output is correct |
6 | Correct | 7 ms | 512 KB | Output is correct |
7 | Correct | 14 ms | 768 KB | Output is correct |
8 | Correct | 6 ms | 512 KB | Output is correct |
9 | Correct | 62 ms | 3372 KB | Output is correct |
10 | Correct | 7 ms | 512 KB | Output is correct |
11 | Correct | 6 ms | 512 KB | Output is correct |
12 | Correct | 83 ms | 3704 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 | 360 KB | Output is correct |
4 | Correct | 8 ms | 512 KB | Output is correct |
5 | Correct | 6 ms | 416 KB | Output is correct |
6 | Correct | 12 ms | 556 KB | Output is correct |
7 | Correct | 10 ms | 768 KB | Output is correct |
8 | Correct | 7 ms | 512 KB | Output is correct |
9 | Correct | 60 ms | 3464 KB | Output is correct |
10 | Correct | 7 ms | 512 KB | Output is correct |
11 | Correct | 6 ms | 512 KB | Output is correct |
12 | Correct | 75 ms | 3704 KB | Output is correct |
13 | Correct | 60 ms | 6136 KB | Output is correct |
14 | Correct | 65 ms | 5240 KB | Output is correct |
15 | Correct | 59 ms | 4868 KB | Output is correct |
16 | Correct | 62 ms | 6160 KB | Output is correct |
17 | Correct | 62 ms | 5112 KB | Output is correct |
18 | Correct | 62 ms | 5344 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 360 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 8 ms | 512 KB | Output is correct |
5 | Correct | 7 ms | 432 KB | Output is correct |
6 | Correct | 7 ms | 528 KB | Output is correct |
7 | Correct | 14 ms | 768 KB | Output is correct |
8 | Correct | 6 ms | 512 KB | Output is correct |
9 | Correct | 62 ms | 3388 KB | Output is correct |
10 | Correct | 6 ms | 512 KB | Output is correct |
11 | Correct | 7 ms | 512 KB | Output is correct |
12 | Correct | 52 ms | 3704 KB | Output is correct |
13 | Correct | 66 ms | 6136 KB | Output is correct |
14 | Correct | 58 ms | 5252 KB | Output is correct |
15 | Correct | 63 ms | 4732 KB | Output is correct |
16 | Correct | 60 ms | 6152 KB | Output is correct |
17 | Correct | 72 ms | 5124 KB | Output is correct |
18 | Correct | 64 ms | 5368 KB | Output is correct |
19 | Correct | 367 ms | 25264 KB | Output is correct |
20 | Correct | 374 ms | 21236 KB | Output is correct |
21 | Correct | 350 ms | 19808 KB | Output is correct |
22 | Correct | 405 ms | 25380 KB | Output is correct |
23 | Correct | 222 ms | 13764 KB | Output is correct |
24 | Correct | 439 ms | 20572 KB | Output is correct |
25 | Correct | 339 ms | 21672 KB | Output is correct |