/*
File created on 05/27/2021 at 15:50:04.
Link to problem: https://oj.uz/problem/view/BOI14_postmen
Description: Hierholzer's algorithm for eulerian cycle + separation in "mini" cycles
Time complexity: O(N+M)
Space complexity: O(N+M)
Status: TLE
Copyright: Ⓒ 2021 Francois Vogel
*/
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
using namespace std;
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ins insert
#define ll long long
signed main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int n, nbEdges;
cin >> n >> nbEdges;
vector<pii> graph [n];
for (int i = 0; i < nbEdges; i++) {
int nodeA, nodeB;
cin >> nodeA >> nodeB;
nodeA--;
nodeB--;
graph[nodeA].pb(pii(nodeB, i));
graph[nodeB].pb(pii(nodeA, i));
}
bool usedEdge [nbEdges];
memset(usedEdge, false, nbEdges);
vector<int> circuit, path, st;
bool as [n];
memset(as, false, n);
path.pb(0);
while (!path.empty()) {
while (!graph[path.back()].empty() and usedEdge[graph[path.back()].back().s]) graph[path.back()].pop_back();
if (graph[path.back()].empty()) {
circuit.pb(path.back());
path.pop_back();
int i = circuit.back();
if (as[i]) {
while (st.back() != i) {
as[st.back()] = false;
cout << st.back()+1 << " ";
st.pop_back();
}
st.pop_back();
cout << i+1 << " " << endl;
}
as[i] = true;
st.pb(i);
}
else {
usedEdge[graph[path.back()].back().s] = true;
int nn = graph[path.back()].back().f;
graph[path.back()].pop_back();
path.pb(nn);
}
}
int d = 0;
d++;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
4 ms |
460 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
3 ms |
460 KB |
Output is correct |
7 |
Correct |
7 ms |
972 KB |
Output is correct |
8 |
Correct |
2 ms |
460 KB |
Output is correct |
9 |
Correct |
41 ms |
3740 KB |
Output is correct |
10 |
Correct |
4 ms |
460 KB |
Output is correct |
11 |
Correct |
3 ms |
460 KB |
Output is correct |
12 |
Correct |
56 ms |
4120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
4 ms |
460 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
3 ms |
460 KB |
Output is correct |
7 |
Correct |
7 ms |
972 KB |
Output is correct |
8 |
Correct |
2 ms |
460 KB |
Output is correct |
9 |
Correct |
42 ms |
3776 KB |
Output is correct |
10 |
Correct |
4 ms |
460 KB |
Output is correct |
11 |
Correct |
3 ms |
460 KB |
Output is correct |
12 |
Correct |
49 ms |
4144 KB |
Output is correct |
13 |
Correct |
66 ms |
8184 KB |
Output is correct |
14 |
Correct |
91 ms |
6696 KB |
Output is correct |
15 |
Correct |
103 ms |
6688 KB |
Output is correct |
16 |
Correct |
54 ms |
8200 KB |
Output is correct |
17 |
Correct |
127 ms |
5948 KB |
Output is correct |
18 |
Correct |
94 ms |
6888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
4 ms |
460 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
3 ms |
460 KB |
Output is correct |
7 |
Correct |
7 ms |
972 KB |
Output is correct |
8 |
Correct |
2 ms |
460 KB |
Output is correct |
9 |
Correct |
41 ms |
3768 KB |
Output is correct |
10 |
Correct |
4 ms |
460 KB |
Output is correct |
11 |
Correct |
4 ms |
476 KB |
Output is correct |
12 |
Correct |
47 ms |
4176 KB |
Output is correct |
13 |
Correct |
52 ms |
8128 KB |
Output is correct |
14 |
Correct |
91 ms |
6708 KB |
Output is correct |
15 |
Correct |
107 ms |
6596 KB |
Output is correct |
16 |
Correct |
61 ms |
8172 KB |
Output is correct |
17 |
Correct |
122 ms |
5908 KB |
Output is correct |
18 |
Correct |
94 ms |
6836 KB |
Output is correct |
19 |
Correct |
427 ms |
39456 KB |
Output is correct |
20 |
Execution timed out |
626 ms |
31924 KB |
Time limit exceeded |
21 |
Halted |
0 ms |
0 KB |
- |