# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
208735 | 2020-03-12T05:45:28 Z | E869120 | Senior Postmen (BOI14_postmen) | C++14 | 500 ms | 45304 KB |
#include <iostream> #include <vector> #include <set> using namespace std; #pragma warning (disable: 4996) struct Node { int to, cap, rev; }; int N, M, A[500009], B[500009], deg[500009], cv[500009]; vector<Node> X[500009]; int cur[500009]; bool used[500009]; int vec[500009], sz; int v1[500009], sz1; int main() { scanf("%d%d", &N, &M); for (int i = 1; i <= M; i++) { scanf("%d%d", &A[i], &B[i]); deg[A[i]]++; deg[B[i]]++; } for (int i = 1; i <= N; i++) X[i].resize(deg[i]); for (int i = 1; i <= M; i++) { X[A[i]][cv[A[i]]] = Node{ B[i], 1, cv[B[i]] }; cv[A[i]]++; X[B[i]][cv[B[i]]] = Node{ A[i], 1, cv[A[i]] - 1 }; cv[B[i]]++; } int num = M, cnt = 1; while (num > 0) { while (true) { while (cur[cnt] < X[cnt].size() && X[cnt][cur[cnt]].cap == 0) cur[cnt]++; if (cur[cnt] < X[cnt].size()) break; cnt++; } int cx = cnt; sz = 0; while (true) { vec[sz] = cx; sz++; int nex = -1, res = -1; while (X[cx][cur[cx]].cap == 0) cur[cx]++; nex = X[cx][cur[cx]].to; res = X[cx][cur[cx]].rev; X[cx][cur[cx]].cap = 0; X[nex][res].cap = 0; num--; if (nex == cnt) break; cx = nex; } vec[sz] = cnt; sz++; for (int i = 0; i < sz; i++) used[vec[i]] = false; sz1 = 0; for (int i = 0; i < sz; i++) { if (used[vec[i]] == true) { int num = 0; while (true) { int cp = v1[sz1 - 1]; if (num) printf(" "); printf("%d", cp); num++; used[cp] = false; sz1--; if (cp == vec[i]) break; } printf("\n"); } used[vec[i]] = true; v1[sz1] = vec[i]; sz1++; } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 12100 KB | Output is correct |
2 | Correct | 14 ms | 12160 KB | Output is correct |
3 | Correct | 15 ms | 12104 KB | Output is correct |
4 | Correct | 18 ms | 12288 KB | Output is correct |
5 | Correct | 15 ms | 12160 KB | Output is correct |
6 | Correct | 15 ms | 12288 KB | Output is correct |
7 | Correct | 22 ms | 12648 KB | Output is correct |
8 | Correct | 14 ms | 12288 KB | Output is correct |
9 | Correct | 55 ms | 15584 KB | Output is correct |
10 | Correct | 14 ms | 12288 KB | Output is correct |
11 | Correct | 13 ms | 12288 KB | Output is correct |
12 | Correct | 63 ms | 15792 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 12160 KB | Output is correct |
2 | Correct | 13 ms | 12136 KB | Output is correct |
3 | Correct | 11 ms | 12136 KB | Output is correct |
4 | Correct | 18 ms | 12212 KB | Output is correct |
5 | Correct | 12 ms | 12136 KB | Output is correct |
6 | Correct | 13 ms | 12288 KB | Output is correct |
7 | Correct | 18 ms | 12672 KB | Output is correct |
8 | Correct | 13 ms | 12288 KB | Output is correct |
9 | Correct | 56 ms | 15660 KB | Output is correct |
10 | Correct | 14 ms | 12288 KB | Output is correct |
11 | Correct | 16 ms | 12264 KB | Output is correct |
12 | Correct | 62 ms | 15808 KB | Output is correct |
13 | Correct | 70 ms | 18680 KB | Output is correct |
14 | Correct | 69 ms | 17564 KB | Output is correct |
15 | Correct | 66 ms | 17148 KB | Output is correct |
16 | Correct | 66 ms | 18656 KB | Output is correct |
17 | Correct | 86 ms | 17268 KB | Output is correct |
18 | Correct | 66 ms | 18028 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 12160 KB | Output is correct |
2 | Correct | 13 ms | 12160 KB | Output is correct |
3 | Correct | 12 ms | 12160 KB | Output is correct |
4 | Correct | 13 ms | 12288 KB | Output is correct |
5 | Correct | 12 ms | 12160 KB | Output is correct |
6 | Correct | 13 ms | 12288 KB | Output is correct |
7 | Correct | 18 ms | 12692 KB | Output is correct |
8 | Correct | 14 ms | 12288 KB | Output is correct |
9 | Correct | 53 ms | 15608 KB | Output is correct |
10 | Correct | 17 ms | 12288 KB | Output is correct |
11 | Correct | 12 ms | 12288 KB | Output is correct |
12 | Correct | 76 ms | 15736 KB | Output is correct |
13 | Correct | 86 ms | 18664 KB | Output is correct |
14 | Correct | 69 ms | 17528 KB | Output is correct |
15 | Correct | 71 ms | 17144 KB | Output is correct |
16 | Correct | 75 ms | 18680 KB | Output is correct |
17 | Correct | 89 ms | 17272 KB | Output is correct |
18 | Correct | 83 ms | 18016 KB | Output is correct |
19 | Correct | 402 ms | 45280 KB | Output is correct |
20 | Correct | 395 ms | 39752 KB | Output is correct |
21 | Correct | 374 ms | 37208 KB | Output is correct |
22 | Correct | 380 ms | 45304 KB | Output is correct |
23 | Correct | 234 ms | 29688 KB | Output is correct |
24 | Execution timed out | 509 ms | 38392 KB | Time limit exceeded |
25 | Halted | 0 ms | 0 KB | - |