# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
558193 | 2022-05-07T03:17:53 Z | Shelter | Senior Postmen (BOI14_postmen) | C++17 | 446 ms | 92232 KB |
#include<bits/stdc++.h> using namespace std; #define ii pair<int, int> #define vi vector<int> #define F first #define S second #define endl '\n' #define int long long const int maxn = 5e5 + 5; int n, m, pt[maxn]; vector<ii> g[maxn]; bool used[maxn], vs[maxn]; vector<int> ans; void hier(int u) { while(pt[u] < g[u].size()) { int id = g[u][pt[u]].S, v = g[u][pt[u]].F; if(!used[id]) { used[id] = 1; hier(v); } ++pt[u]; } ans.emplace_back(u); } vector<vi> decompose() { stack<int> cur; vector<vi> re; for(int u: ans) { if(!vs[u]) { cur.push(u); vs[u] = 1; } else { vi cyc; while(vs[u]) { cyc.emplace_back(cur.top()); vs[cur.top()] = 0; cur.pop(); } re.emplace_back(cyc); cur.push(u); vs[u] = 1; } } return re; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 1; i <= m; i++) { int u, v; cin >> u >> v; g[u].emplace_back(v, i); g[v].emplace_back(u, i); } hier(1); auto t = decompose(); for(auto cyc: t) { for(int u: cyc) { cout << u << ' '; } cout << endl; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 11988 KB | Output is correct |
2 | Correct | 7 ms | 12052 KB | Output is correct |
3 | Correct | 7 ms | 12080 KB | Output is correct |
4 | Correct | 8 ms | 12500 KB | Output is correct |
5 | Correct | 7 ms | 12176 KB | Output is correct |
6 | Correct | 7 ms | 12612 KB | Output is correct |
7 | Correct | 12 ms | 14152 KB | Output is correct |
8 | Correct | 8 ms | 12424 KB | Output is correct |
9 | Correct | 39 ms | 23228 KB | Output is correct |
10 | Correct | 8 ms | 12380 KB | Output is correct |
11 | Correct | 7 ms | 12352 KB | Output is correct |
12 | Correct | 40 ms | 23960 KB | Output is correct |
# | 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 | 7 ms | 11988 KB | Output is correct |
4 | Correct | 8 ms | 12488 KB | Output is correct |
5 | Correct | 7 ms | 12244 KB | Output is correct |
6 | Correct | 7 ms | 12628 KB | Output is correct |
7 | Correct | 12 ms | 14164 KB | Output is correct |
8 | Correct | 7 ms | 12372 KB | Output is correct |
9 | Correct | 40 ms | 23260 KB | Output is correct |
10 | Correct | 8 ms | 12372 KB | Output is correct |
11 | Correct | 8 ms | 12440 KB | Output is correct |
12 | Correct | 41 ms | 24000 KB | Output is correct |
13 | Correct | 61 ms | 27412 KB | Output is correct |
14 | Correct | 65 ms | 24276 KB | Output is correct |
15 | Correct | 58 ms | 26684 KB | Output is correct |
16 | Correct | 71 ms | 27460 KB | Output is correct |
17 | Correct | 65 ms | 22264 KB | Output is correct |
18 | Correct | 61 ms | 25360 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 12084 KB | Output is correct |
2 | Correct | 6 ms | 12072 KB | Output is correct |
3 | Correct | 8 ms | 11992 KB | Output is correct |
4 | Correct | 8 ms | 12520 KB | Output is correct |
5 | Correct | 7 ms | 12220 KB | Output is correct |
6 | Correct | 8 ms | 12628 KB | Output is correct |
7 | Correct | 12 ms | 14036 KB | Output is correct |
8 | Correct | 7 ms | 12372 KB | Output is correct |
9 | Correct | 36 ms | 23320 KB | Output is correct |
10 | Correct | 8 ms | 12372 KB | Output is correct |
11 | Correct | 8 ms | 12352 KB | Output is correct |
12 | Correct | 44 ms | 24052 KB | Output is correct |
13 | Correct | 63 ms | 27448 KB | Output is correct |
14 | Correct | 68 ms | 24260 KB | Output is correct |
15 | Correct | 58 ms | 26724 KB | Output is correct |
16 | Correct | 60 ms | 27460 KB | Output is correct |
17 | Correct | 64 ms | 22336 KB | Output is correct |
18 | Correct | 63 ms | 25364 KB | Output is correct |
19 | Correct | 391 ms | 89128 KB | Output is correct |
20 | Correct | 400 ms | 73824 KB | Output is correct |
21 | Correct | 380 ms | 84260 KB | Output is correct |
22 | Correct | 397 ms | 92232 KB | Output is correct |
23 | Correct | 161 ms | 66176 KB | Output is correct |
24 | Correct | 446 ms | 63252 KB | Output is correct |
25 | Correct | 430 ms | 79592 KB | Output is correct |