# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
543921 | 2022-03-31T15:34:07 Z | Olympia | Senior Postmen (BOI14_postmen) | C++14 | 500 ms | 16916 KB |
#include <vector> #include <algorithm> #include <iostream> #include <set> #include <cmath> #include <map> #include <random> #include <cassert> #include <ctime> #include <stack> #include <cstdlib> #include <queue> #include <cstdio> #include <limits.h> using namespace std; vector<pair<int,int>> adj[(int)5e5]; bool hasVisited[(int)5e5]; bool okay[(int)5e5]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N, M; scanf("%d%d", &N, &M); for (int i = 0; i < M; i++) { int u, v; scanf("%d%d", &u, &v); u--, v--; adj[u].emplace_back(v, i), adj[v].emplace_back(u, i); } for (int i = 0; i < M; i++) { okay[i] = true; } stack<pair<int,int>> nodes; for (int i = 0; i < N; i++) { nodes.push({i, -1}); while (!nodes.empty()) { int cur = nodes.top().first; okay[nodes.top().second] = false; hasVisited[cur] = true; bool upd = false; for (pair<int,int> &pr: adj[cur]) { int j = pr.first; if (pr.second == nodes.top().second || !okay[pr.second]) { continue; } okay[pr.second] = false; if (hasVisited[j]) { while (!nodes.empty() && nodes.top().first != j) { hasVisited[nodes.top().first] = false; printf("%d ", nodes.top().first + 1); nodes.pop(); } printf("%d\n", j + 1); } else { nodes.emplace(j, pr.second); } upd = true; break; } if (!upd) { nodes.pop(); } } } }
Compilation message
# | 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 | 7 ms | 11988 KB | Output is correct |
4 | Correct | 8 ms | 12116 KB | Output is correct |
5 | Correct | 9 ms | 11988 KB | Output is correct |
6 | Correct | 8 ms | 12116 KB | Output is correct |
7 | Correct | 13 ms | 12500 KB | Output is correct |
8 | Correct | 7 ms | 12116 KB | Output is correct |
9 | Correct | 59 ms | 14520 KB | Output is correct |
10 | Correct | 8 ms | 12116 KB | Output is correct |
11 | Correct | 8 ms | 12160 KB | Output is correct |
12 | Correct | 52 ms | 14796 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 12076 KB | Output is correct |
2 | Correct | 7 ms | 11988 KB | Output is correct |
3 | Correct | 6 ms | 11988 KB | Output is correct |
4 | Correct | 8 ms | 12116 KB | Output is correct |
5 | Correct | 6 ms | 12116 KB | Output is correct |
6 | Correct | 8 ms | 12116 KB | Output is correct |
7 | Correct | 11 ms | 12500 KB | Output is correct |
8 | Correct | 8 ms | 12116 KB | Output is correct |
9 | Correct | 86 ms | 14460 KB | Output is correct |
10 | Correct | 7 ms | 12116 KB | Output is correct |
11 | Correct | 8 ms | 12116 KB | Output is correct |
12 | Correct | 43 ms | 14744 KB | Output is correct |
13 | Correct | 62 ms | 16916 KB | Output is correct |
14 | Correct | 82 ms | 15568 KB | Output is correct |
15 | Execution timed out | 812 ms | 15480 KB | Time limit exceeded |
16 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 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 | 9 ms | 12116 KB | Output is correct |
5 | Correct | 7 ms | 12116 KB | Output is correct |
6 | Correct | 8 ms | 12332 KB | Output is correct |
7 | Correct | 12 ms | 12628 KB | Output is correct |
8 | Correct | 7 ms | 12168 KB | Output is correct |
9 | Correct | 58 ms | 14440 KB | Output is correct |
10 | Correct | 8 ms | 12116 KB | Output is correct |
11 | Correct | 8 ms | 12116 KB | Output is correct |
12 | Correct | 51 ms | 14764 KB | Output is correct |
13 | Correct | 57 ms | 16716 KB | Output is correct |
14 | Correct | 55 ms | 15676 KB | Output is correct |
15 | Execution timed out | 829 ms | 15492 KB | Time limit exceeded |
16 | Halted | 0 ms | 0 KB | - |