# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
419704 | 2021-06-07T11:43:19 Z | VladM | Senior Postmen (BOI14_postmen) | C++14 | 354 ms | 30252 KB |
/* Official solution for postmen. Complexity O(N + M) Author: Kestutis Vilcinskas */ #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 | 0 ms | 332 KB | Output is correct |
2 | Correct | 0 ms | 332 KB | Output is correct |
3 | Correct | 0 ms | 332 KB | Output is correct |
4 | Correct | 1 ms | 332 KB | Output is correct |
5 | Correct | 1 ms | 332 KB | Output is correct |
6 | Correct | 2 ms | 332 KB | Output is correct |
7 | Correct | 8 ms | 588 KB | Output is correct |
8 | Correct | 1 ms | 332 KB | Output is correct |
9 | Correct | 46 ms | 2580 KB | Output is correct |
10 | Correct | 2 ms | 332 KB | Output is correct |
11 | Correct | 2 ms | 332 KB | Output is correct |
12 | Correct | 51 ms | 2684 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 2 ms | 332 KB | Output is correct |
5 | Correct | 1 ms | 332 KB | Output is correct |
6 | Correct | 2 ms | 332 KB | Output is correct |
7 | Correct | 6 ms | 588 KB | Output is correct |
8 | Correct | 1 ms | 384 KB | Output is correct |
9 | Correct | 41 ms | 2624 KB | Output is correct |
10 | Correct | 3 ms | 332 KB | Output is correct |
11 | Correct | 1 ms | 332 KB | Output is correct |
12 | Correct | 43 ms | 2684 KB | Output is correct |
13 | Correct | 51 ms | 4904 KB | Output is correct |
14 | Correct | 55 ms | 4120 KB | Output is correct |
15 | Correct | 48 ms | 3864 KB | Output is correct |
16 | Correct | 51 ms | 4876 KB | Output is correct |
17 | Correct | 57 ms | 3920 KB | Output is correct |
18 | Correct | 52 ms | 4136 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 332 KB | Output is correct |
2 | Correct | 0 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 2 ms | 332 KB | Output is correct |
5 | Correct | 1 ms | 332 KB | Output is correct |
6 | Correct | 2 ms | 332 KB | Output is correct |
7 | Correct | 6 ms | 588 KB | Output is correct |
8 | Correct | 1 ms | 332 KB | Output is correct |
9 | Correct | 39 ms | 2664 KB | Output is correct |
10 | Correct | 2 ms | 332 KB | Output is correct |
11 | Correct | 2 ms | 332 KB | Output is correct |
12 | Correct | 41 ms | 2692 KB | Output is correct |
13 | Correct | 63 ms | 4828 KB | Output is correct |
14 | Correct | 47 ms | 4036 KB | Output is correct |
15 | Correct | 42 ms | 3808 KB | Output is correct |
16 | Correct | 47 ms | 4804 KB | Output is correct |
17 | Correct | 61 ms | 3888 KB | Output is correct |
18 | Correct | 46 ms | 4208 KB | Output is correct |
19 | Correct | 298 ms | 23656 KB | Output is correct |
20 | Correct | 285 ms | 26268 KB | Output is correct |
21 | Correct | 289 ms | 23108 KB | Output is correct |
22 | Correct | 304 ms | 30252 KB | Output is correct |
23 | Correct | 199 ms | 15796 KB | Output is correct |
24 | Correct | 354 ms | 24972 KB | Output is correct |
25 | Correct | 315 ms | 26492 KB | Output is correct |