#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define mp make_pair
using namespace std;
const int maxn = 500100;
int in() {
char c=getchar_unlocked();
while(c<'0'||c>'9')
c=getchar_unlocked();
int r=0;
while(c>='0'&&c<='9') {
r=r*10+c-'0';
c=getchar_unlocked();
}
return r;
}
void out(int x) {
int lz=0, r=0;
while(x%10==0) {
++lz;
x/=10;
}
while(x) {
r=r*10+x%10;
x/=10;
}
while(r) {
putchar_unlocked('0'+r%10);
r/=10;
}
while(lz--)
putchar_unlocked('0');
}
class edge {
public:
int nxt_node;
list<edge>::iterator reverse_edge;
edge(int _node) {
nxt_node = _node;
}
};
list<edge>adj[maxn];
int n, m;
vector<int>euler_tour;
bool visited[maxn];
void solve(int node) {
while(adj[node].size() > 0) {
edge x = adj[node].front();
int nxt = x.nxt_node;
adj[nxt].erase(x.reverse_edge);
adj[node].pop_front();
solve(nxt);
}
euler_tour.pb(node);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
n = in();
m = in();
int a, b;
for(int i=0;i<m;i++) {
a = in(); b = in();
adj[a].pf(edge(b));
list<edge>::iterator it_a = adj[a].begin();
adj[b].pf(edge(a));
list<edge>::iterator it_b = adj[b].begin();
it_a->reverse_edge = it_b;
it_b->reverse_edge = it_a;
}
solve(1);
vector<int>seq;
for(int i:euler_tour) {
//cout<<i<<" ";
if(!visited[i]) {
seq.pb(i);
visited[i] = true;
}
else {
// go back in seq while you find i
while(seq.size() > 0 && seq.back() != i) {
visited[seq.back()] = false;
out(seq.back());
putchar_unlocked(' ');
seq.pop_back();
}
out(i);
putchar_unlocked('\n');
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
12032 KB |
Output is correct |
2 |
Correct |
12 ms |
12032 KB |
Output is correct |
3 |
Correct |
11 ms |
12032 KB |
Output is correct |
4 |
Correct |
12 ms |
12544 KB |
Output is correct |
5 |
Correct |
14 ms |
12288 KB |
Output is correct |
6 |
Correct |
12 ms |
12672 KB |
Output is correct |
7 |
Correct |
15 ms |
14208 KB |
Output is correct |
8 |
Correct |
12 ms |
12416 KB |
Output is correct |
9 |
Correct |
48 ms |
26104 KB |
Output is correct |
10 |
Correct |
13 ms |
12544 KB |
Output is correct |
11 |
Correct |
16 ms |
12416 KB |
Output is correct |
12 |
Correct |
45 ms |
26208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
12032 KB |
Output is correct |
2 |
Correct |
13 ms |
12160 KB |
Output is correct |
3 |
Correct |
13 ms |
12080 KB |
Output is correct |
4 |
Correct |
13 ms |
12464 KB |
Output is correct |
5 |
Correct |
17 ms |
12288 KB |
Output is correct |
6 |
Correct |
13 ms |
12672 KB |
Output is correct |
7 |
Correct |
20 ms |
14208 KB |
Output is correct |
8 |
Correct |
13 ms |
12356 KB |
Output is correct |
9 |
Correct |
46 ms |
26080 KB |
Output is correct |
10 |
Correct |
17 ms |
12416 KB |
Output is correct |
11 |
Correct |
12 ms |
12416 KB |
Output is correct |
12 |
Correct |
49 ms |
26104 KB |
Output is correct |
13 |
Correct |
78 ms |
26104 KB |
Output is correct |
14 |
Correct |
85 ms |
24184 KB |
Output is correct |
15 |
Correct |
70 ms |
26232 KB |
Output is correct |
16 |
Correct |
85 ms |
26336 KB |
Output is correct |
17 |
Correct |
87 ms |
23104 KB |
Output is correct |
18 |
Correct |
77 ms |
25724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
12032 KB |
Output is correct |
2 |
Correct |
11 ms |
12032 KB |
Output is correct |
3 |
Correct |
14 ms |
12032 KB |
Output is correct |
4 |
Correct |
13 ms |
12520 KB |
Output is correct |
5 |
Correct |
11 ms |
12288 KB |
Output is correct |
6 |
Correct |
30 ms |
12672 KB |
Output is correct |
7 |
Correct |
18 ms |
14208 KB |
Output is correct |
8 |
Correct |
12 ms |
12416 KB |
Output is correct |
9 |
Correct |
51 ms |
26268 KB |
Output is correct |
10 |
Correct |
13 ms |
12544 KB |
Output is correct |
11 |
Correct |
15 ms |
12416 KB |
Output is correct |
12 |
Correct |
47 ms |
26104 KB |
Output is correct |
13 |
Correct |
91 ms |
26232 KB |
Output is correct |
14 |
Correct |
81 ms |
24164 KB |
Output is correct |
15 |
Correct |
75 ms |
26232 KB |
Output is correct |
16 |
Correct |
83 ms |
26232 KB |
Output is correct |
17 |
Correct |
79 ms |
23096 KB |
Output is correct |
18 |
Correct |
96 ms |
25704 KB |
Output is correct |
19 |
Correct |
425 ms |
82576 KB |
Output is correct |
20 |
Correct |
435 ms |
72004 KB |
Output is correct |
21 |
Correct |
372 ms |
82524 KB |
Output is correct |
22 |
Correct |
425 ms |
82552 KB |
Output is correct |
23 |
Correct |
195 ms |
82316 KB |
Output is correct |
24 |
Correct |
450 ms |
66824 KB |
Output is correct |
25 |
Correct |
444 ms |
78904 KB |
Output is correct |