# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
734548 | 2023-05-02T15:39:12 Z | DAleksa | Senior Postmen (BOI14_postmen) | C++17 | 454 ms | 77552 KB |
#include <bits/stdc++.h> using namespace std; struct edge { int v; int id; }; const int N = 5e5 + 10; vector<edge> g[N]; int n, m; vector<int> eulerian_cycle; bool mark[N]; int cnt[N]; int id = 0; stack<int> stk; int idx[N]; void find_eulerian_cycle(int u) { for(; idx[u] < (int)g[u].size(); idx[u]++) { edge v = g[u][idx[u]]; if(mark[v.id]) continue; mark[v.id] = true; find_eulerian_cycle(v.v); eulerian_cycle.push_back(v.v); } } int main() { scanf("%d%d", &n, &m); for(int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); // int I = i / 3; // if(i % 3 == 0) { // u = 1; // v = 2 * I + 2; // } else if(i % 3 == 1) { // u = 1; // v = 2 * I + 3; // } else { // u = 2 * I + 2; // v = 2 * I + 3; // } g[u].push_back({v, id}); g[v].push_back({u, id++}); } find_eulerian_cycle(1); eulerian_cycle.push_back(1); //for(int i = 0; i < eulerian_cycle.size(); i++) printf("%d ", eulerian_cycle[i]); //printf("\n\n"); stk.push(eulerian_cycle[0]); cnt[eulerian_cycle[0]]++; for(int i = 1; i < eulerian_cycle.size(); i++) { if(cnt[eulerian_cycle[i]] > 0) { printf("%d ", eulerian_cycle[i]); while(stk.top() != eulerian_cycle[i]) { printf("%d ", stk.top()); cnt[stk.top()]--; stk.pop(); } printf("\n"); } else { cnt[eulerian_cycle[i]]++; stk.push(eulerian_cycle[i]); } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 11988 KB | Output is correct |
2 | Correct | 7 ms | 11988 KB | Output is correct |
3 | Correct | 6 ms | 11988 KB | Output is correct |
4 | Correct | 7 ms | 12372 KB | Output is correct |
5 | Correct | 9 ms | 12144 KB | Output is correct |
6 | Correct | 8 ms | 12544 KB | Output is correct |
7 | Correct | 12 ms | 13652 KB | Output is correct |
8 | Correct | 10 ms | 12244 KB | Output is correct |
9 | Correct | 39 ms | 21188 KB | Output is correct |
10 | Correct | 7 ms | 12244 KB | Output is correct |
11 | Correct | 7 ms | 12244 KB | Output is correct |
12 | Correct | 43 ms | 21540 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 11988 KB | Output is correct |
2 | Correct | 6 ms | 12000 KB | Output is correct |
3 | Correct | 6 ms | 11988 KB | Output is correct |
4 | Correct | 8 ms | 12372 KB | Output is correct |
5 | Correct | 6 ms | 12116 KB | Output is correct |
6 | Correct | 8 ms | 12500 KB | Output is correct |
7 | Correct | 15 ms | 13680 KB | Output is correct |
8 | Correct | 9 ms | 12244 KB | Output is correct |
9 | Correct | 44 ms | 21268 KB | Output is correct |
10 | Correct | 8 ms | 12240 KB | Output is correct |
11 | Correct | 8 ms | 12244 KB | Output is correct |
12 | Correct | 47 ms | 21608 KB | Output is correct |
13 | Correct | 66 ms | 23640 KB | Output is correct |
14 | Correct | 58 ms | 19860 KB | Output is correct |
15 | Correct | 56 ms | 22880 KB | Output is correct |
16 | Correct | 64 ms | 24844 KB | Output is correct |
17 | Correct | 61 ms | 18504 KB | Output is correct |
18 | Correct | 66 ms | 22544 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 11988 KB | Output is correct |
2 | Correct | 6 ms | 11988 KB | Output is correct |
3 | Correct | 6 ms | 11988 KB | Output is correct |
4 | Correct | 8 ms | 12372 KB | Output is correct |
5 | Correct | 7 ms | 12116 KB | Output is correct |
6 | Correct | 9 ms | 12500 KB | Output is correct |
7 | Correct | 12 ms | 13652 KB | Output is correct |
8 | Correct | 7 ms | 12272 KB | Output is correct |
9 | Correct | 44 ms | 21224 KB | Output is correct |
10 | Correct | 8 ms | 12244 KB | Output is correct |
11 | Correct | 8 ms | 12244 KB | Output is correct |
12 | Correct | 47 ms | 21632 KB | Output is correct |
13 | Correct | 68 ms | 23764 KB | Output is correct |
14 | Correct | 58 ms | 19948 KB | Output is correct |
15 | Correct | 67 ms | 22848 KB | Output is correct |
16 | Correct | 63 ms | 24752 KB | Output is correct |
17 | Correct | 58 ms | 18364 KB | Output is correct |
18 | Correct | 68 ms | 22532 KB | Output is correct |
19 | Correct | 454 ms | 77552 KB | Output is correct |
20 | Correct | 393 ms | 58472 KB | Output is correct |
21 | Correct | 364 ms | 71280 KB | Output is correct |
22 | Correct | 451 ms | 77452 KB | Output is correct |
23 | Correct | 194 ms | 60424 KB | Output is correct |
24 | Correct | 426 ms | 43544 KB | Output is correct |
25 | Correct | 403 ms | 65628 KB | Output is correct |