# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
39996 | 2018-01-25T07:13:52 Z | Waschbar | Senior Postmen (BOI14_postmen) | C++14 | 422 ms | 23776 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 | 6 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 | 6 ms | 384 KB | Output is correct |
6 | Correct | 7 ms | 512 KB | Output is correct |
7 | Correct | 11 ms | 764 KB | Output is correct |
8 | Correct | 5 ms | 504 KB | Output is correct |
9 | Correct | 40 ms | 2680 KB | Output is correct |
10 | Correct | 6 ms | 512 KB | Output is correct |
11 | Correct | 6 ms | 512 KB | Output is correct |
12 | Correct | 50 ms | 2784 KB | Output is correct |
# | Verdict | Execution time | Memory | 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 | 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 | 13 ms | 768 KB | Output is correct |
8 | Correct | 5 ms | 384 KB | Output is correct |
9 | Correct | 51 ms | 2680 KB | Output is correct |
10 | Correct | 6 ms | 512 KB | Output is correct |
11 | Correct | 7 ms | 512 KB | Output is correct |
12 | Correct | 57 ms | 2912 KB | Output is correct |
13 | Correct | 52 ms | 4984 KB | Output is correct |
14 | Correct | 69 ms | 4216 KB | Output is correct |
15 | Correct | 50 ms | 3832 KB | Output is correct |
16 | Correct | 52 ms | 4984 KB | Output is correct |
17 | Correct | 65 ms | 3960 KB | Output is correct |
18 | Correct | 51 ms | 4196 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 | 384 KB | Output is correct |
6 | Correct | 6 ms | 512 KB | Output is correct |
7 | Correct | 11 ms | 768 KB | Output is correct |
8 | Correct | 7 ms | 512 KB | Output is correct |
9 | Correct | 63 ms | 2680 KB | Output is correct |
10 | Correct | 7 ms | 512 KB | Output is correct |
11 | Correct | 6 ms | 512 KB | Output is correct |
12 | Correct | 49 ms | 2784 KB | Output is correct |
13 | Correct | 52 ms | 4908 KB | Output is correct |
14 | Correct | 57 ms | 4212 KB | Output is correct |
15 | Correct | 55 ms | 3936 KB | Output is correct |
16 | Correct | 50 ms | 4984 KB | Output is correct |
17 | Correct | 67 ms | 4064 KB | Output is correct |
18 | Correct | 59 ms | 4216 KB | Output is correct |
19 | Correct | 374 ms | 23772 KB | Output is correct |
20 | Correct | 327 ms | 19772 KB | Output is correct |
21 | Correct | 343 ms | 18292 KB | Output is correct |
22 | Correct | 360 ms | 23776 KB | Output is correct |
23 | Correct | 208 ms | 12024 KB | Output is correct |
24 | Correct | 422 ms | 18896 KB | Output is correct |
25 | Correct | 331 ms | 20108 KB | Output is correct |