// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
#define SZ(x) (int) x.size()
#define F first
#define S second
const int N = 5e5 + 10;
int P[N], R[N], M[N], ptr[N], from[N], to[N], n, m; vector<int> adj[N], tr;
void tour(int v) {
while (ptr[v] < SZ(adj[v])) {
int id = adj[v][ptr[v]++]; int u = from[id] ^ v ^ to[id];
if (!M[id]) M[id] = 1, tour(u);
}
tr.push_back(v);
}
int Find(int v) {
return !~P[v] ? v : P[v] = Find(P[v]);
}
void Union(int u, int v) {
u = Find(u), v = Find(v);
if (u == v) return;
P[u] = v, R[v] = max(R[u], R[v]);
}
int main() {
memset(P, -1, sizeof P);
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &from[i], &to[i]);
adj[from[i]].push_back(i);
adj[to[i]].push_back(i);
}
tour(1);
for (int i = 0; i <= SZ(tr); i++) R[i] = i;
memset(M, -1, sizeof M);
for (int i = 0; i < SZ(tr) && R[Find(0)] != SZ(tr) - 1; i = R[Find(i + 1)]) {
if (~M[tr[i]]) {
for (int j = M[tr[i]]; j < i; j = R[Find(j + 1)]) {
printf("%d ", tr[j]), M[tr[j]] = -1;
Union(j, R[Find(j + 1)]);
}
printf("\n");
M[tr[i]] = i;
} else M[tr[i]] = i;
}
return 0;
}
Compilation message
postmen.cpp:3: warning: ignoring #pragma comment [-Wunknown-pragmas]
3 | #pragma comment(linker, "/stack:200000000")
|
postmen.cpp: In function 'int main()':
postmen.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
39 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
41 | scanf("%d%d", &from[i], &to[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
15980 KB |
Output is correct |
2 |
Correct |
12 ms |
15980 KB |
Output is correct |
3 |
Correct |
12 ms |
15980 KB |
Output is correct |
4 |
Correct |
14 ms |
16364 KB |
Output is correct |
5 |
Correct |
11 ms |
16252 KB |
Output is correct |
6 |
Correct |
12 ms |
16492 KB |
Output is correct |
7 |
Correct |
17 ms |
17516 KB |
Output is correct |
8 |
Correct |
12 ms |
16236 KB |
Output is correct |
9 |
Correct |
60 ms |
25448 KB |
Output is correct |
10 |
Correct |
14 ms |
16236 KB |
Output is correct |
11 |
Correct |
11 ms |
16236 KB |
Output is correct |
12 |
Correct |
63 ms |
25728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
15980 KB |
Output is correct |
2 |
Correct |
11 ms |
15980 KB |
Output is correct |
3 |
Correct |
10 ms |
15980 KB |
Output is correct |
4 |
Correct |
13 ms |
16364 KB |
Output is correct |
5 |
Correct |
11 ms |
16108 KB |
Output is correct |
6 |
Correct |
14 ms |
16492 KB |
Output is correct |
7 |
Correct |
18 ms |
17516 KB |
Output is correct |
8 |
Correct |
12 ms |
16236 KB |
Output is correct |
9 |
Correct |
62 ms |
25324 KB |
Output is correct |
10 |
Correct |
12 ms |
16236 KB |
Output is correct |
11 |
Correct |
14 ms |
16236 KB |
Output is correct |
12 |
Correct |
71 ms |
25580 KB |
Output is correct |
13 |
Correct |
85 ms |
28012 KB |
Output is correct |
14 |
Correct |
92 ms |
24256 KB |
Output is correct |
15 |
Correct |
107 ms |
27108 KB |
Output is correct |
16 |
Correct |
91 ms |
28012 KB |
Output is correct |
17 |
Correct |
113 ms |
21604 KB |
Output is correct |
18 |
Correct |
101 ms |
25576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
16108 KB |
Output is correct |
2 |
Correct |
11 ms |
15980 KB |
Output is correct |
3 |
Correct |
10 ms |
15980 KB |
Output is correct |
4 |
Correct |
12 ms |
16364 KB |
Output is correct |
5 |
Correct |
11 ms |
16108 KB |
Output is correct |
6 |
Correct |
13 ms |
16492 KB |
Output is correct |
7 |
Correct |
18 ms |
17516 KB |
Output is correct |
8 |
Correct |
12 ms |
16236 KB |
Output is correct |
9 |
Correct |
62 ms |
25324 KB |
Output is correct |
10 |
Correct |
12 ms |
16236 KB |
Output is correct |
11 |
Correct |
15 ms |
16236 KB |
Output is correct |
12 |
Correct |
69 ms |
25584 KB |
Output is correct |
13 |
Correct |
96 ms |
28012 KB |
Output is correct |
14 |
Correct |
102 ms |
24040 KB |
Output is correct |
15 |
Correct |
89 ms |
27120 KB |
Output is correct |
16 |
Correct |
96 ms |
28148 KB |
Output is correct |
17 |
Correct |
97 ms |
21604 KB |
Output is correct |
18 |
Correct |
115 ms |
25672 KB |
Output is correct |
19 |
Execution timed out |
634 ms |
76244 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |