# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
31524 | 2017-08-29T07:26:26 Z | aome | Senior Postmen (BOI14_postmen) | C++11 | 500 ms | 106548 KB |
/*input 5 10 1 5 1 3 2 4 2 5 2 3 1 2 3 4 4 5 3 5 1 4 10 15 1 3 5 1 2 3 9 2 3 4 6 3 4 5 7 4 4 8 5 7 8 5 6 7 7 8 8 10 10 9 */ #include <algorithm> #include <bitset> #include <cassert> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <fstream> #include <functional> #include <iomanip> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <utility> #include <vector> using namespace std; #define sp ' ' #define endl '\n' #define fi first #define se second #define mp make_pair #define N 500005 struct data { int u; list<data>::iterator it; data(int _u): u(_u) {}; }; int n, m; list<data> a[N]; deque<int> path; void add_edge(int u, int v) { a[u].push_front(data(v)); a[v].push_front(data(u)); a[u].begin()->it = a[v].begin(); a[v].begin()->it = a[u].begin(); } ostream& operator << (ostream &os, vector<int>&x) { for (int i = 0; i < x.size(); i++) { os << x[i]; if (i != x.size() - 1) os << sp; } return os; } ostream& operator << (ostream &os, pair<int, int> x) { cout << x.fi << sp << x.se << sp; return os; } ostream& operator << (ostream &os, vector<pair<int, int> >&x) { for (int i = 0; i < x.size(); i++) os << x[i] << endl; return os; } bool in[N]; vector<vector<int> > ans; void find_path(int u) { while (a[u].size() > 0) { int v = a[u].front().u; list<data>::iterator it = a[u].front().it; a[v].erase(it); a[u].pop_front(); find_path(v); } vector<int> tmp; if (in[u]) { while (!path.empty() && path.back() != u) { tmp.push_back(path.back()); in[path.back()] = false; path.pop_back(); } tmp.push_back(path.back()); in[path.back()] = false; path.pop_back(); ans.push_back(tmp); } path.push_back(u); in[u] = true; } signed main() { // #ifdef UncleGrandpa // freopen("input.txt", "r", stdin); // #endif scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) { int u, v; scanf("%d %d", &u, &v); add_edge(u, v); } find_path(1); for (int i = 0; i < ans.size(); i++) { for (int j = 0; j < ans[i].size(); j++) { printf("%d", ans[i][j]); if (j != ans[i].size() - 1) printf(" "); } printf("\n"); } // for (int i = 0; i < path.size(); i++) cout << path[i] << sp; // cout << endl; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 12032 KB | Output is correct |
2 | Correct | 24 ms | 12032 KB | Output is correct |
3 | Correct | 13 ms | 12032 KB | Output is correct |
4 | Correct | 13 ms | 12672 KB | Output is correct |
5 | Correct | 13 ms | 12208 KB | Output is correct |
6 | Correct | 13 ms | 12928 KB | Output is correct |
7 | Correct | 26 ms | 14976 KB | Output is correct |
8 | Correct | 13 ms | 12392 KB | Output is correct |
9 | Correct | 101 ms | 31192 KB | Output is correct |
10 | Correct | 14 ms | 12544 KB | Output is correct |
11 | Correct | 13 ms | 12544 KB | Output is correct |
12 | Correct | 99 ms | 31240 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 12084 KB | Output is correct |
2 | Correct | 12 ms | 12032 KB | Output is correct |
3 | Correct | 13 ms | 12032 KB | Output is correct |
4 | Correct | 16 ms | 12672 KB | Output is correct |
5 | Correct | 17 ms | 12264 KB | Output is correct |
6 | Correct | 17 ms | 12928 KB | Output is correct |
7 | Correct | 23 ms | 14976 KB | Output is correct |
8 | Correct | 16 ms | 12392 KB | Output is correct |
9 | Correct | 83 ms | 31200 KB | Output is correct |
10 | Correct | 16 ms | 12520 KB | Output is correct |
11 | Correct | 16 ms | 12592 KB | Output is correct |
12 | Correct | 101 ms | 31228 KB | Output is correct |
13 | Correct | 111 ms | 30920 KB | Output is correct |
14 | Correct | 128 ms | 27580 KB | Output is correct |
15 | Correct | 119 ms | 31432 KB | Output is correct |
16 | Correct | 131 ms | 30948 KB | Output is correct |
17 | Correct | 166 ms | 24000 KB | Output is correct |
18 | Correct | 139 ms | 29988 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 12160 KB | Output is correct |
2 | Correct | 12 ms | 12032 KB | Output is correct |
3 | Correct | 12 ms | 12032 KB | Output is correct |
4 | Correct | 14 ms | 12672 KB | Output is correct |
5 | Correct | 13 ms | 12288 KB | Output is correct |
6 | Correct | 17 ms | 12960 KB | Output is correct |
7 | Correct | 27 ms | 14944 KB | Output is correct |
8 | Correct | 13 ms | 12416 KB | Output is correct |
9 | Correct | 98 ms | 31216 KB | Output is correct |
10 | Correct | 18 ms | 12544 KB | Output is correct |
11 | Correct | 14 ms | 12544 KB | Output is correct |
12 | Correct | 98 ms | 31224 KB | Output is correct |
13 | Correct | 126 ms | 30972 KB | Output is correct |
14 | Correct | 128 ms | 27552 KB | Output is correct |
15 | Correct | 127 ms | 31360 KB | Output is correct |
16 | Correct | 136 ms | 30968 KB | Output is correct |
17 | Correct | 127 ms | 23968 KB | Output is correct |
18 | Correct | 148 ms | 30096 KB | Output is correct |
19 | Execution timed out | 637 ms | 106548 KB | Time limit exceeded |
20 | Halted | 0 ms | 0 KB | - |