// 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], L[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;
if (L[u] > L[v]) swap(u, v);
P[u] = v, L[v] = L[v] + L[u], 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++) L[i] = 1, R[i] = i;
memset(M, -1, sizeof M);
for (int i = 0; i < SZ(tr) && L[Find(0)] != SZ(tr); i = R[Find(i + 1)]) {
//printf("i %d\n", i);
if (~M[tr[i]]) {
int l = M[tr[i]];
for (int j = M[tr[i]]; j < i; j = R[Find(j + 1)]) {
//printf("j %d\n", j);
printf("%d ", tr[j]), M[tr[j]] = -1;
}
printf("\n");
for (int j = l; j < i; j = R[Find(j + 1)]) {
Union(j, R[Find(j + 1)]);
}
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:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
40 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
42 | scanf("%d%d", &from[i], &to[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
15980 KB |
Output is correct |
2 |
Correct |
10 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 |
10 ms |
16256 KB |
Output is correct |
6 |
Correct |
12 ms |
16492 KB |
Output is correct |
7 |
Correct |
17 ms |
17644 KB |
Output is correct |
8 |
Correct |
11 ms |
16236 KB |
Output is correct |
9 |
Correct |
61 ms |
25708 KB |
Output is correct |
10 |
Correct |
11 ms |
16236 KB |
Output is correct |
11 |
Correct |
11 ms |
16236 KB |
Output is correct |
12 |
Correct |
63 ms |
25964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
15980 KB |
Output is correct |
2 |
Correct |
11 ms |
15980 KB |
Output is correct |
3 |
Correct |
12 ms |
15980 KB |
Output is correct |
4 |
Correct |
13 ms |
16364 KB |
Output is correct |
5 |
Correct |
10 ms |
16108 KB |
Output is correct |
6 |
Correct |
14 ms |
16492 KB |
Output is correct |
7 |
Correct |
20 ms |
17644 KB |
Output is correct |
8 |
Correct |
13 ms |
16236 KB |
Output is correct |
9 |
Correct |
58 ms |
25708 KB |
Output is correct |
10 |
Correct |
13 ms |
16236 KB |
Output is correct |
11 |
Correct |
14 ms |
16236 KB |
Output is correct |
12 |
Correct |
62 ms |
25964 KB |
Output is correct |
13 |
Correct |
89 ms |
28524 KB |
Output is correct |
14 |
Correct |
110 ms |
24424 KB |
Output is correct |
15 |
Correct |
88 ms |
27492 KB |
Output is correct |
16 |
Correct |
91 ms |
28524 KB |
Output is correct |
17 |
Correct |
93 ms |
21988 KB |
Output is correct |
18 |
Correct |
90 ms |
26088 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
15980 KB |
Output is correct |
2 |
Correct |
10 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 |
17 ms |
17644 KB |
Output is correct |
8 |
Correct |
11 ms |
16236 KB |
Output is correct |
9 |
Correct |
66 ms |
25708 KB |
Output is correct |
10 |
Correct |
12 ms |
16236 KB |
Output is correct |
11 |
Correct |
13 ms |
16236 KB |
Output is correct |
12 |
Correct |
62 ms |
25964 KB |
Output is correct |
13 |
Correct |
103 ms |
28524 KB |
Output is correct |
14 |
Correct |
90 ms |
24424 KB |
Output is correct |
15 |
Correct |
82 ms |
27492 KB |
Output is correct |
16 |
Correct |
87 ms |
28524 KB |
Output is correct |
17 |
Correct |
91 ms |
21988 KB |
Output is correct |
18 |
Correct |
94 ms |
26088 KB |
Output is correct |
19 |
Execution timed out |
610 ms |
78168 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |