#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#ifdef WAIMAI
#include "grader.cpp"
#else
#include "simurgh.h"
#endif
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
const int SIZE = 505;
const int MSIZ = SIZE * SIZE / 2;
int n, m;
bool ed[MSIZ];
int h[SIZE], pa[SIZE], pid[SIZE];
vector<pair<int, int>> adj[SIZE];
int to[MSIZ], ty[MSIZ];
int dsu(int x) {
return x == to[x] ? x : (to[x] = dsu(to[x]));
}
void merge(int a, int b) {
a = dsu(a), b = dsu(b);
if (a == b) return;
to[b] = a;
ty[a] = (ty[a] != 2 ? ty[a] : ty[b]);
}
int que() {
vector<int> id;
FOR (i, 0, m - 1) if (ed[i]) id.pb(i);
// cout << "que : "; for (int i : id) cout << i << ' '; cout << '\n';
int c = count_common_roads(id);
// debug(c);
return c;
}
vector<int> find_roads(int n_, vector<int> u, vector<int> v) {
n = n_, m = u.size();
FOR (i, 1, n) {
adj[i].clear();
h[i] = pa[i] = pid[i] = -1;
}
FOR (i, 0, m - 1) {
ed[i] = 0;
u[i]++, v[i]++;
adj[u[i]].pb(v[i], i);
adj[v[i]].pb(u[i], i);
}
auto dfs = [&](auto dfs, int pos)->void {
for (auto [np, id] : adj[pos]) if (h[np] == -1) {
h[np] = h[pos] + 1;
pa[np] = pos;
pid[np] = id;
ed[id] = 1;
dfs(dfs, np);
}
};
h[1] = 1, dfs(dfs, 1);
FOR (i, 0, m - 1) {
to[i] = i;
ty[i] = 2;
}
int tot = que();
FOR (i, 0, m - 1) if (ed[i] == 0) {
int x = u[i], y = v[i];
while (x != y) {
if (h[x] < h[y]) swap(x, y);
int j = pid[x];
if (dsu(i) != dsu(j) && (ty[dsu(i)] == 2 || ty[dsu(j)] == 2)) {
ed[i] = 1, ed[j] = 0;
int cur = que();
if (cur == tot) merge(i, j);
else {
ty[dsu(j)] = (cur > tot ? 0 : 1);
ty[dsu(i)] = (cur > tot ? 1 : 0);
}
ed[i] = 0, ed[j] = 1;
}
x = pa[x];
}
}
vector<int> ans;
FOR (i, 0, m - 1) if (ty[dsu(i)]) ans.pb(i);
// cout << "ans : "; for (int i : ans) cout << i << " \n"[i == ans.back()];
return ans;
}
/*
in1
4 6
0 1
0 2
0 3
1 2
1 3
2 3
0 1 5
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
correct |
2 |
Correct |
0 ms |
348 KB |
correct |
3 |
Correct |
0 ms |
348 KB |
correct |
4 |
Correct |
0 ms |
348 KB |
correct |
5 |
Correct |
0 ms |
348 KB |
correct |
6 |
Correct |
0 ms |
348 KB |
correct |
7 |
Correct |
0 ms |
348 KB |
correct |
8 |
Correct |
0 ms |
348 KB |
correct |
9 |
Correct |
0 ms |
348 KB |
correct |
10 |
Correct |
0 ms |
348 KB |
correct |
11 |
Correct |
0 ms |
348 KB |
correct |
12 |
Correct |
0 ms |
348 KB |
correct |
13 |
Correct |
0 ms |
348 KB |
correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
correct |
2 |
Correct |
0 ms |
348 KB |
correct |
3 |
Correct |
0 ms |
348 KB |
correct |
4 |
Correct |
0 ms |
348 KB |
correct |
5 |
Correct |
0 ms |
348 KB |
correct |
6 |
Correct |
0 ms |
348 KB |
correct |
7 |
Correct |
0 ms |
348 KB |
correct |
8 |
Correct |
0 ms |
348 KB |
correct |
9 |
Correct |
0 ms |
348 KB |
correct |
10 |
Correct |
0 ms |
348 KB |
correct |
11 |
Correct |
0 ms |
348 KB |
correct |
12 |
Correct |
0 ms |
348 KB |
correct |
13 |
Correct |
0 ms |
348 KB |
correct |
14 |
Correct |
2 ms |
348 KB |
correct |
15 |
Correct |
2 ms |
348 KB |
correct |
16 |
Correct |
2 ms |
548 KB |
correct |
17 |
Correct |
2 ms |
348 KB |
correct |
18 |
Correct |
1 ms |
348 KB |
correct |
19 |
Correct |
2 ms |
348 KB |
correct |
20 |
Correct |
1 ms |
348 KB |
correct |
21 |
Correct |
1 ms |
348 KB |
correct |
22 |
Correct |
1 ms |
348 KB |
correct |
23 |
Correct |
1 ms |
344 KB |
correct |
24 |
Correct |
1 ms |
348 KB |
correct |
25 |
Correct |
1 ms |
348 KB |
correct |
26 |
Correct |
1 ms |
348 KB |
correct |
27 |
Correct |
1 ms |
452 KB |
correct |
28 |
Correct |
0 ms |
460 KB |
correct |
29 |
Correct |
0 ms |
348 KB |
correct |
30 |
Correct |
1 ms |
348 KB |
correct |
31 |
Correct |
1 ms |
348 KB |
correct |
32 |
Correct |
1 ms |
348 KB |
correct |
33 |
Correct |
1 ms |
348 KB |
correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
correct |
2 |
Correct |
0 ms |
348 KB |
correct |
3 |
Correct |
0 ms |
348 KB |
correct |
4 |
Correct |
0 ms |
348 KB |
correct |
5 |
Correct |
0 ms |
348 KB |
correct |
6 |
Correct |
0 ms |
348 KB |
correct |
7 |
Correct |
0 ms |
348 KB |
correct |
8 |
Correct |
0 ms |
348 KB |
correct |
9 |
Correct |
0 ms |
348 KB |
correct |
10 |
Correct |
0 ms |
348 KB |
correct |
11 |
Correct |
0 ms |
348 KB |
correct |
12 |
Correct |
0 ms |
348 KB |
correct |
13 |
Correct |
0 ms |
348 KB |
correct |
14 |
Correct |
2 ms |
348 KB |
correct |
15 |
Correct |
2 ms |
348 KB |
correct |
16 |
Correct |
2 ms |
548 KB |
correct |
17 |
Correct |
2 ms |
348 KB |
correct |
18 |
Correct |
1 ms |
348 KB |
correct |
19 |
Correct |
2 ms |
348 KB |
correct |
20 |
Correct |
1 ms |
348 KB |
correct |
21 |
Correct |
1 ms |
348 KB |
correct |
22 |
Correct |
1 ms |
348 KB |
correct |
23 |
Correct |
1 ms |
344 KB |
correct |
24 |
Correct |
1 ms |
348 KB |
correct |
25 |
Correct |
1 ms |
348 KB |
correct |
26 |
Correct |
1 ms |
348 KB |
correct |
27 |
Correct |
1 ms |
452 KB |
correct |
28 |
Correct |
0 ms |
460 KB |
correct |
29 |
Correct |
0 ms |
348 KB |
correct |
30 |
Correct |
1 ms |
348 KB |
correct |
31 |
Correct |
1 ms |
348 KB |
correct |
32 |
Correct |
1 ms |
348 KB |
correct |
33 |
Correct |
1 ms |
348 KB |
correct |
34 |
Correct |
638 ms |
2128 KB |
correct |
35 |
Correct |
571 ms |
1896 KB |
correct |
36 |
Correct |
281 ms |
1628 KB |
correct |
37 |
Correct |
4 ms |
348 KB |
correct |
38 |
Correct |
599 ms |
1884 KB |
correct |
39 |
Correct |
459 ms |
1816 KB |
correct |
40 |
Correct |
286 ms |
1636 KB |
correct |
41 |
Correct |
632 ms |
1936 KB |
correct |
42 |
Correct |
597 ms |
1884 KB |
correct |
43 |
Correct |
184 ms |
1416 KB |
correct |
44 |
Correct |
126 ms |
1116 KB |
correct |
45 |
Correct |
166 ms |
1112 KB |
correct |
46 |
Correct |
103 ms |
1116 KB |
correct |
47 |
Correct |
25 ms |
604 KB |
correct |
48 |
Correct |
1 ms |
504 KB |
correct |
49 |
Correct |
5 ms |
348 KB |
correct |
50 |
Correct |
24 ms |
776 KB |
correct |
51 |
Correct |
168 ms |
1180 KB |
correct |
52 |
Correct |
125 ms |
1112 KB |
correct |
53 |
Correct |
111 ms |
1060 KB |
correct |
54 |
Correct |
203 ms |
1368 KB |
correct |
55 |
Correct |
170 ms |
1204 KB |
correct |
56 |
Correct |
171 ms |
1200 KB |
correct |
57 |
Correct |
167 ms |
1116 KB |
correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
correct |
2 |
Correct |
0 ms |
348 KB |
correct |
3 |
Incorrect |
687 ms |
4840 KB |
WA in grader: NO |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
correct |
2 |
Correct |
0 ms |
348 KB |
correct |
3 |
Correct |
0 ms |
348 KB |
correct |
4 |
Correct |
0 ms |
348 KB |
correct |
5 |
Correct |
0 ms |
348 KB |
correct |
6 |
Correct |
0 ms |
348 KB |
correct |
7 |
Correct |
0 ms |
348 KB |
correct |
8 |
Correct |
0 ms |
348 KB |
correct |
9 |
Correct |
0 ms |
348 KB |
correct |
10 |
Correct |
0 ms |
348 KB |
correct |
11 |
Correct |
0 ms |
348 KB |
correct |
12 |
Correct |
0 ms |
348 KB |
correct |
13 |
Correct |
0 ms |
348 KB |
correct |
14 |
Correct |
2 ms |
348 KB |
correct |
15 |
Correct |
2 ms |
348 KB |
correct |
16 |
Correct |
2 ms |
548 KB |
correct |
17 |
Correct |
2 ms |
348 KB |
correct |
18 |
Correct |
1 ms |
348 KB |
correct |
19 |
Correct |
2 ms |
348 KB |
correct |
20 |
Correct |
1 ms |
348 KB |
correct |
21 |
Correct |
1 ms |
348 KB |
correct |
22 |
Correct |
1 ms |
348 KB |
correct |
23 |
Correct |
1 ms |
344 KB |
correct |
24 |
Correct |
1 ms |
348 KB |
correct |
25 |
Correct |
1 ms |
348 KB |
correct |
26 |
Correct |
1 ms |
348 KB |
correct |
27 |
Correct |
1 ms |
452 KB |
correct |
28 |
Correct |
0 ms |
460 KB |
correct |
29 |
Correct |
0 ms |
348 KB |
correct |
30 |
Correct |
1 ms |
348 KB |
correct |
31 |
Correct |
1 ms |
348 KB |
correct |
32 |
Correct |
1 ms |
348 KB |
correct |
33 |
Correct |
1 ms |
348 KB |
correct |
34 |
Correct |
638 ms |
2128 KB |
correct |
35 |
Correct |
571 ms |
1896 KB |
correct |
36 |
Correct |
281 ms |
1628 KB |
correct |
37 |
Correct |
4 ms |
348 KB |
correct |
38 |
Correct |
599 ms |
1884 KB |
correct |
39 |
Correct |
459 ms |
1816 KB |
correct |
40 |
Correct |
286 ms |
1636 KB |
correct |
41 |
Correct |
632 ms |
1936 KB |
correct |
42 |
Correct |
597 ms |
1884 KB |
correct |
43 |
Correct |
184 ms |
1416 KB |
correct |
44 |
Correct |
126 ms |
1116 KB |
correct |
45 |
Correct |
166 ms |
1112 KB |
correct |
46 |
Correct |
103 ms |
1116 KB |
correct |
47 |
Correct |
25 ms |
604 KB |
correct |
48 |
Correct |
1 ms |
504 KB |
correct |
49 |
Correct |
5 ms |
348 KB |
correct |
50 |
Correct |
24 ms |
776 KB |
correct |
51 |
Correct |
168 ms |
1180 KB |
correct |
52 |
Correct |
125 ms |
1112 KB |
correct |
53 |
Correct |
111 ms |
1060 KB |
correct |
54 |
Correct |
203 ms |
1368 KB |
correct |
55 |
Correct |
170 ms |
1204 KB |
correct |
56 |
Correct |
171 ms |
1200 KB |
correct |
57 |
Correct |
167 ms |
1116 KB |
correct |
58 |
Correct |
0 ms |
348 KB |
correct |
59 |
Correct |
0 ms |
348 KB |
correct |
60 |
Incorrect |
687 ms |
4840 KB |
WA in grader: NO |
61 |
Halted |
0 ms |
0 KB |
- |