#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("bmi,bmi2,lzcnt,popcnt") // bit manipulation
#pragma GCC target("movbe") // byte swap
#pragma GCC target("aes,pclmul,rdrnd") // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")
typedef long long ll;
#define rep(i, a, b) for (int i = (a); i < int(b); i++)
#define rrep(i, a, b) for (int i = (a) - 1; i >= int(b); i--)
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define pb push_back
inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }
ll INF = 1000000000;
ll mod = 1e9 + 7;
#define int ll
#define float double
//
int N, M;
vector<vector<pii>> graph;
vector<bool> visited_node, visited_edge;
vector<vector<int>> tours;
vector<int> tour;
int dfs(int node) {
// cerr << "enter " << node + 1 << "\n";
visited_node[node] = true;
int ret = -1;
while (true) {
rrep(i, graph[node].size(), 0) {
// cerr << "edge " << graph[node][i].first << " " << graph[node][i].second + 1 << "\n";
if (visited_edge[graph[node][i].first]) graph[node].pop_back();
else if (visited_node[graph[node][i].second]) {
visited_edge[graph[node][i].first] = true;
ret = graph[node][i].second;
graph[node].pop_back();
break;
}
else {
visited_edge[graph[node][i].first] = true;
int n = graph[node][i].second;
graph[node].pop_back();
ret = dfs(n);
break;
}
}
if (ret == node) {
tour.pb(node);
tours.pb(tour);
tour.clear(); //
ret = -1;
}
else if (ret != -1) {
tour.pb(node);
break;
}
if (graph[node].size() == 0) return -2;
}
//
visited_node[node] = false;
// cerr << "leaving " << node + 1 << "\n";
return ret;
}
int32_t main()
{
fast();
cin >> N >> M;
graph.assign(N, {});
int a, b;
int e = 0;
rep(i,0,M) {
cin >> a >> b;
a--; b--;
graph[a].pb({e, b});
graph[b].pb({e, a});
e++;
}
// assert even
visited_node.assign(N, false);
visited_edge.assign(M, false);
rep(i,0,N) {
while (graph[i].size() > 0) {
dfs(i);
}
}
rep(i,0,tours.size()) {
rep(j,0,tours[i].size()) {
cout << tours[i][j] + 1 << " ";
}
cout << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
600 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
4 ms |
1116 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
20 ms |
4188 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
22 ms |
4872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
604 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
616 KB |
Output is correct |
7 |
Correct |
4 ms |
1116 KB |
Output is correct |
8 |
Correct |
1 ms |
600 KB |
Output is correct |
9 |
Correct |
19 ms |
4188 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
22 ms |
4756 KB |
Output is correct |
13 |
Correct |
34 ms |
17100 KB |
Output is correct |
14 |
Correct |
31 ms |
8460 KB |
Output is correct |
15 |
Correct |
28 ms |
8084 KB |
Output is correct |
16 |
Correct |
38 ms |
17104 KB |
Output is correct |
17 |
Correct |
33 ms |
8452 KB |
Output is correct |
18 |
Correct |
32 ms |
10452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
568 KB |
Output is correct |
7 |
Correct |
4 ms |
1116 KB |
Output is correct |
8 |
Correct |
2 ms |
604 KB |
Output is correct |
9 |
Correct |
20 ms |
4188 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
22 ms |
4904 KB |
Output is correct |
13 |
Correct |
36 ms |
17108 KB |
Output is correct |
14 |
Correct |
34 ms |
8460 KB |
Output is correct |
15 |
Correct |
29 ms |
7888 KB |
Output is correct |
16 |
Correct |
35 ms |
17008 KB |
Output is correct |
17 |
Correct |
33 ms |
8456 KB |
Output is correct |
18 |
Correct |
42 ms |
10440 KB |
Output is correct |
19 |
Correct |
323 ms |
84852 KB |
Output is correct |
20 |
Correct |
262 ms |
42496 KB |
Output is correct |
21 |
Correct |
233 ms |
38452 KB |
Output is correct |
22 |
Correct |
334 ms |
85020 KB |
Output is correct |
23 |
Correct |
125 ms |
18572 KB |
Output is correct |
24 |
Correct |
304 ms |
42808 KB |
Output is correct |
25 |
Correct |
324 ms |
51416 KB |
Output is correct |