#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
#define X first
#define Y second
int n, m;
vector<int> G[507];
int deg[507];
vector<int> ok[507];
int p[507], h[507];
int correct[507];
bool tree_edge[507][507];
int edge_nr[507][507];
vector<int> T;
int edge_corr[507 * 507 / 2];
bool vis[507];
ii edgev[507 * 507 / 2];
void dfs(int w) {
for(int u : G[w]) {
if(!vis[u]) {
vis[u] = 1;
p[u] = w;
h[u] = h[w] + 1;
tree_edge[w][u] = tree_edge[u][w] = 1;
T.push_back(edge_nr[w][u]);
dfs(u);
}
}
}
void check_path(int a, int b) {
int c = b;
while(c != a && correct[c] == -1)
c = p[c];
if(c == b)
return ;
vector<int> base, cycle;
bool in_cycle[507 * 507 / 2];
memset(in_cycle, 0, sizeof in_cycle);
int w = b;
while(h[w] > h[a]) {
in_cycle[edge_nr[w][p[w]]] = true;
cycle.push_back(edge_nr[w][p[w]]);
w = p[w];
}
cycle.push_back(edge_nr[a][b]);
for(int x : T)
if(!in_cycle[x])
base.push_back(x);
if(c == a) {
vector<int> res;
int minv = 1e9, maxv = -1;
for(int x : cycle) {
vector<int> tmp = base;
for(int y : cycle)
if(x != y)
tmp.push_back(y);
res.push_back(count_common_roads(tmp));
minv = min(minv, res.back());
maxv = max(maxv, res.back());
}
if(minv == maxv) {
int w = b;
while(h[w] > h[a]) {
correct[w] = 0;
w = p[w];
}
} else {
for(int i = 0 ; i < cycle.size() ; i++)
if(res[i] == minv)
edge_corr[cycle[i]] = 1;
else
edge_corr[cycle[i]] = 0;
int w = b;
while(h[w] > h[a]) {
correct[w] = edge_corr[edge_nr[w][p[w]]];
w = p[w];
}
}
return ;
}
int known = correct[c];
int knownv;
vector<int> tmp = base;
for(int x : cycle)
if(x != edge_nr[c][p[c]])
tmp.push_back(x);
knownv = count_common_roads(tmp);
w = b;
while(w != c) {
tmp = base;
for(int x : cycle)
if(x != edge_nr[w][p[w]])
tmp.push_back(x);
int res = count_common_roads(tmp);
if(res == knownv)
correct[w] = known;
else
correct[w] = (known + 1) % 2;
w = p[w];
}
}
struct FindUnion {
int p[507];
FindUnion() {
for(int i = 0 ; i < n ; i++)
p[i] = i;
}
int Find(int x) {
if(p[x] == x)
return x;
return p[x] = Find(p[x]);
}
void Union(int x, int y) {
int a = Find(x);
int b = Find(y);
if(a == b)
return ;
p[a] = b;
}
};
int count_common(vector<int> F) {
int sub = 0;
FindUnion FU;
for(int e : F) {
FU.Union(edgev[e].X, edgev[e].Y);
}
for(int e : T) {
if(FU.Find(edgev[e].X) != FU.Find(edgev[e].Y)) {
sub += edge_corr[e];
FU.Union(edgev[e].X, edgev[e].Y);
F.push_back(e);
}
}
int res = count_common_roads(F);
return res - sub;
}
int find_one(int w, int a, int b) {
if(a == b)
return a;
int mid = (a + b) / 2;
vector<int> F;
for(int i = a ; i <= mid ; i++) {
int u = G[w][i];
if(!ok[w][i])
F.push_back(edge_nr[w][u]);
}
if(count_common(F))
return find_one(w, a, mid);
return find_one(w, mid + 1, b);
}
std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
::n = n;
m = u.size();
for(int i = 0 ; i < m ; i++) {
G[u[i]].push_back(v[i]);
G[v[i]].push_back(u[i]);
edge_nr[u[i]][v[i]] = edge_nr[v[i]][u[i]] = i;
edgev[i] = {u[i], v[i]};
}
vis[0] = 1;
dfs(0);
memset(correct, -1, sizeof correct);
vector<int> E;
for(int i = 0 ; i < m ; i++)
if(!tree_edge[u[i]][v[i]])
E.push_back(i);
sort(E.begin(), E.end(), [&u, &v](int a, int b) {
int lcpha = min(h[u[a]], h[v[a]]);
int lcphb = min(h[u[b]], h[v[b]]);
if(lcpha != lcphb)
return lcpha < lcphb;
return a < b;
});
for(int e : E) {
int a = u[e];
int b = v[e];
if(h[a] > h[b])
swap(a, b);
check_path(a, b);
}
for(int i = 1 ; i < n ; i++) {
if(correct[i] == -1)
correct[i] = 1;
edge_corr[edge_nr[i][p[i]]] = correct[i];
}
for(int i = 0 ; i < n ; i++) {
vector<int> tmp;
for(int x : G[i])
tmp.push_back(edge_nr[i][x]);
deg[i] = count_common(tmp);
ok[i].resize(G[i].size(), 0);
}
vector<int> res;
while(res.size() + 1 < n) {
for(int i = 0 ; i < n ; i++) {
if(deg[i] == 1) {
int x = find_one(i, 0, G[i].size());
ok[i][x] = 1;
int u = G[i][x];
for(int j = 0 ; j < G[u].size() ; j++) {
if(G[u][j] == i) {
ok[u][j] = 1;
break;
}
}
res.push_back(edge_nr[i][u]);
deg[u]--;
deg[i]--;
break;
}
}
}
return res;
}
Compilation message
simurgh.cpp: In function 'void check_path(int, int)':
simurgh.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < cycle.size() ; i++)
~~^~~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:231:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(res.size() + 1 < n) {
~~~~~~~~~~~~~~~^~~
simurgh.cpp:237:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0 ; j < G[u].size() ; j++) {
~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
correct |
2 |
Correct |
2 ms |
504 KB |
correct |
3 |
Correct |
2 ms |
504 KB |
correct |
4 |
Correct |
2 ms |
504 KB |
correct |
5 |
Correct |
2 ms |
504 KB |
correct |
6 |
Correct |
2 ms |
504 KB |
correct |
7 |
Correct |
2 ms |
376 KB |
correct |
8 |
Correct |
2 ms |
504 KB |
correct |
9 |
Correct |
2 ms |
376 KB |
correct |
10 |
Correct |
2 ms |
504 KB |
correct |
11 |
Correct |
2 ms |
376 KB |
correct |
12 |
Correct |
2 ms |
504 KB |
correct |
13 |
Correct |
2 ms |
504 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
correct |
2 |
Correct |
2 ms |
504 KB |
correct |
3 |
Correct |
2 ms |
504 KB |
correct |
4 |
Correct |
2 ms |
504 KB |
correct |
5 |
Correct |
2 ms |
504 KB |
correct |
6 |
Correct |
2 ms |
504 KB |
correct |
7 |
Correct |
2 ms |
376 KB |
correct |
8 |
Correct |
2 ms |
504 KB |
correct |
9 |
Correct |
2 ms |
376 KB |
correct |
10 |
Correct |
2 ms |
504 KB |
correct |
11 |
Correct |
2 ms |
376 KB |
correct |
12 |
Correct |
2 ms |
504 KB |
correct |
13 |
Correct |
2 ms |
504 KB |
correct |
14 |
Correct |
4 ms |
632 KB |
correct |
15 |
Correct |
4 ms |
632 KB |
correct |
16 |
Correct |
4 ms |
760 KB |
correct |
17 |
Correct |
4 ms |
632 KB |
correct |
18 |
Correct |
4 ms |
632 KB |
correct |
19 |
Correct |
5 ms |
632 KB |
correct |
20 |
Correct |
5 ms |
632 KB |
correct |
21 |
Correct |
4 ms |
632 KB |
correct |
22 |
Correct |
4 ms |
632 KB |
correct |
23 |
Correct |
4 ms |
632 KB |
correct |
24 |
Correct |
4 ms |
632 KB |
correct |
25 |
Correct |
3 ms |
632 KB |
correct |
26 |
Correct |
4 ms |
632 KB |
correct |
27 |
Correct |
4 ms |
632 KB |
correct |
28 |
Correct |
3 ms |
632 KB |
correct |
29 |
Correct |
3 ms |
636 KB |
correct |
30 |
Correct |
3 ms |
632 KB |
correct |
31 |
Correct |
4 ms |
676 KB |
correct |
32 |
Correct |
4 ms |
632 KB |
correct |
33 |
Correct |
3 ms |
632 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
correct |
2 |
Correct |
2 ms |
504 KB |
correct |
3 |
Correct |
2 ms |
504 KB |
correct |
4 |
Correct |
2 ms |
504 KB |
correct |
5 |
Correct |
2 ms |
504 KB |
correct |
6 |
Correct |
2 ms |
504 KB |
correct |
7 |
Correct |
2 ms |
376 KB |
correct |
8 |
Correct |
2 ms |
504 KB |
correct |
9 |
Correct |
2 ms |
376 KB |
correct |
10 |
Correct |
2 ms |
504 KB |
correct |
11 |
Correct |
2 ms |
376 KB |
correct |
12 |
Correct |
2 ms |
504 KB |
correct |
13 |
Correct |
2 ms |
504 KB |
correct |
14 |
Correct |
4 ms |
632 KB |
correct |
15 |
Correct |
4 ms |
632 KB |
correct |
16 |
Correct |
4 ms |
760 KB |
correct |
17 |
Correct |
4 ms |
632 KB |
correct |
18 |
Correct |
4 ms |
632 KB |
correct |
19 |
Correct |
5 ms |
632 KB |
correct |
20 |
Correct |
5 ms |
632 KB |
correct |
21 |
Correct |
4 ms |
632 KB |
correct |
22 |
Correct |
4 ms |
632 KB |
correct |
23 |
Correct |
4 ms |
632 KB |
correct |
24 |
Correct |
4 ms |
632 KB |
correct |
25 |
Correct |
3 ms |
632 KB |
correct |
26 |
Correct |
4 ms |
632 KB |
correct |
27 |
Correct |
4 ms |
632 KB |
correct |
28 |
Correct |
3 ms |
632 KB |
correct |
29 |
Correct |
3 ms |
636 KB |
correct |
30 |
Correct |
3 ms |
632 KB |
correct |
31 |
Correct |
4 ms |
676 KB |
correct |
32 |
Correct |
4 ms |
632 KB |
correct |
33 |
Correct |
3 ms |
632 KB |
correct |
34 |
Correct |
51 ms |
2548 KB |
correct |
35 |
Correct |
50 ms |
2680 KB |
correct |
36 |
Correct |
42 ms |
2168 KB |
correct |
37 |
Correct |
17 ms |
1144 KB |
correct |
38 |
Correct |
51 ms |
2780 KB |
correct |
39 |
Correct |
49 ms |
2500 KB |
correct |
40 |
Correct |
44 ms |
2140 KB |
correct |
41 |
Correct |
51 ms |
2644 KB |
correct |
42 |
Correct |
50 ms |
2548 KB |
correct |
43 |
Correct |
38 ms |
2072 KB |
correct |
44 |
Correct |
32 ms |
1784 KB |
correct |
45 |
Correct |
34 ms |
1912 KB |
correct |
46 |
Correct |
32 ms |
1656 KB |
correct |
47 |
Correct |
25 ms |
1404 KB |
correct |
48 |
Correct |
13 ms |
1144 KB |
correct |
49 |
Correct |
17 ms |
1272 KB |
correct |
50 |
Correct |
25 ms |
1420 KB |
correct |
51 |
Correct |
34 ms |
1912 KB |
correct |
52 |
Correct |
32 ms |
1784 KB |
correct |
53 |
Correct |
32 ms |
1656 KB |
correct |
54 |
Correct |
37 ms |
2032 KB |
correct |
55 |
Correct |
39 ms |
1912 KB |
correct |
56 |
Correct |
36 ms |
1940 KB |
correct |
57 |
Correct |
36 ms |
1784 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
correct |
2 |
Correct |
2 ms |
504 KB |
correct |
3 |
Correct |
153 ms |
5928 KB |
correct |
4 |
Correct |
245 ms |
8280 KB |
correct |
5 |
Correct |
252 ms |
8272 KB |
correct |
6 |
Correct |
241 ms |
8176 KB |
correct |
7 |
Correct |
243 ms |
8312 KB |
correct |
8 |
Correct |
249 ms |
8304 KB |
correct |
9 |
Correct |
247 ms |
8308 KB |
correct |
10 |
Correct |
243 ms |
8308 KB |
correct |
11 |
Correct |
246 ms |
8308 KB |
correct |
12 |
Correct |
267 ms |
8308 KB |
correct |
13 |
Correct |
2 ms |
504 KB |
correct |
14 |
Correct |
274 ms |
8312 KB |
correct |
15 |
Correct |
248 ms |
8308 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
correct |
2 |
Correct |
2 ms |
504 KB |
correct |
3 |
Correct |
2 ms |
504 KB |
correct |
4 |
Correct |
2 ms |
504 KB |
correct |
5 |
Correct |
2 ms |
504 KB |
correct |
6 |
Correct |
2 ms |
504 KB |
correct |
7 |
Correct |
2 ms |
376 KB |
correct |
8 |
Correct |
2 ms |
504 KB |
correct |
9 |
Correct |
2 ms |
376 KB |
correct |
10 |
Correct |
2 ms |
504 KB |
correct |
11 |
Correct |
2 ms |
376 KB |
correct |
12 |
Correct |
2 ms |
504 KB |
correct |
13 |
Correct |
2 ms |
504 KB |
correct |
14 |
Correct |
4 ms |
632 KB |
correct |
15 |
Correct |
4 ms |
632 KB |
correct |
16 |
Correct |
4 ms |
760 KB |
correct |
17 |
Correct |
4 ms |
632 KB |
correct |
18 |
Correct |
4 ms |
632 KB |
correct |
19 |
Correct |
5 ms |
632 KB |
correct |
20 |
Correct |
5 ms |
632 KB |
correct |
21 |
Correct |
4 ms |
632 KB |
correct |
22 |
Correct |
4 ms |
632 KB |
correct |
23 |
Correct |
4 ms |
632 KB |
correct |
24 |
Correct |
4 ms |
632 KB |
correct |
25 |
Correct |
3 ms |
632 KB |
correct |
26 |
Correct |
4 ms |
632 KB |
correct |
27 |
Correct |
4 ms |
632 KB |
correct |
28 |
Correct |
3 ms |
632 KB |
correct |
29 |
Correct |
3 ms |
636 KB |
correct |
30 |
Correct |
3 ms |
632 KB |
correct |
31 |
Correct |
4 ms |
676 KB |
correct |
32 |
Correct |
4 ms |
632 KB |
correct |
33 |
Correct |
3 ms |
632 KB |
correct |
34 |
Correct |
51 ms |
2548 KB |
correct |
35 |
Correct |
50 ms |
2680 KB |
correct |
36 |
Correct |
42 ms |
2168 KB |
correct |
37 |
Correct |
17 ms |
1144 KB |
correct |
38 |
Correct |
51 ms |
2780 KB |
correct |
39 |
Correct |
49 ms |
2500 KB |
correct |
40 |
Correct |
44 ms |
2140 KB |
correct |
41 |
Correct |
51 ms |
2644 KB |
correct |
42 |
Correct |
50 ms |
2548 KB |
correct |
43 |
Correct |
38 ms |
2072 KB |
correct |
44 |
Correct |
32 ms |
1784 KB |
correct |
45 |
Correct |
34 ms |
1912 KB |
correct |
46 |
Correct |
32 ms |
1656 KB |
correct |
47 |
Correct |
25 ms |
1404 KB |
correct |
48 |
Correct |
13 ms |
1144 KB |
correct |
49 |
Correct |
17 ms |
1272 KB |
correct |
50 |
Correct |
25 ms |
1420 KB |
correct |
51 |
Correct |
34 ms |
1912 KB |
correct |
52 |
Correct |
32 ms |
1784 KB |
correct |
53 |
Correct |
32 ms |
1656 KB |
correct |
54 |
Correct |
37 ms |
2032 KB |
correct |
55 |
Correct |
39 ms |
1912 KB |
correct |
56 |
Correct |
36 ms |
1940 KB |
correct |
57 |
Correct |
36 ms |
1784 KB |
correct |
58 |
Correct |
2 ms |
376 KB |
correct |
59 |
Correct |
2 ms |
504 KB |
correct |
60 |
Correct |
153 ms |
5928 KB |
correct |
61 |
Correct |
245 ms |
8280 KB |
correct |
62 |
Correct |
252 ms |
8272 KB |
correct |
63 |
Correct |
241 ms |
8176 KB |
correct |
64 |
Correct |
243 ms |
8312 KB |
correct |
65 |
Correct |
249 ms |
8304 KB |
correct |
66 |
Correct |
247 ms |
8308 KB |
correct |
67 |
Correct |
243 ms |
8308 KB |
correct |
68 |
Correct |
246 ms |
8308 KB |
correct |
69 |
Correct |
267 ms |
8308 KB |
correct |
70 |
Correct |
2 ms |
504 KB |
correct |
71 |
Correct |
274 ms |
8312 KB |
correct |
72 |
Correct |
248 ms |
8308 KB |
correct |
73 |
Correct |
3 ms |
504 KB |
correct |
74 |
Correct |
265 ms |
8396 KB |
correct |
75 |
Correct |
265 ms |
8208 KB |
correct |
76 |
Correct |
117 ms |
3832 KB |
correct |
77 |
Correct |
262 ms |
8268 KB |
correct |
78 |
Correct |
254 ms |
8304 KB |
correct |
79 |
Correct |
246 ms |
8308 KB |
correct |
80 |
Correct |
250 ms |
8076 KB |
correct |
81 |
Correct |
230 ms |
7288 KB |
correct |
82 |
Correct |
245 ms |
8056 KB |
correct |
83 |
Correct |
176 ms |
5112 KB |
correct |
84 |
Correct |
178 ms |
5900 KB |
correct |
85 |
Correct |
170 ms |
5500 KB |
correct |
86 |
Correct |
140 ms |
4348 KB |
correct |
87 |
Correct |
124 ms |
3576 KB |
correct |
88 |
Correct |
110 ms |
3192 KB |
correct |
89 |
Correct |
108 ms |
3064 KB |
correct |
90 |
Correct |
108 ms |
2936 KB |
correct |
91 |
Correct |
63 ms |
2060 KB |
correct |
92 |
Correct |
46 ms |
1784 KB |
correct |
93 |
Correct |
165 ms |
5572 KB |
correct |
94 |
Correct |
137 ms |
4344 KB |
correct |
95 |
Correct |
142 ms |
4212 KB |
correct |
96 |
Correct |
106 ms |
3152 KB |
correct |
97 |
Correct |
111 ms |
3168 KB |
correct |
98 |
Correct |
125 ms |
3576 KB |
correct |
99 |
Correct |
109 ms |
3208 KB |
correct |
100 |
Correct |
75 ms |
2188 KB |
correct |
101 |
Correct |
44 ms |
1788 KB |
correct |
102 |
Correct |
167 ms |
5108 KB |
correct |
103 |
Correct |
171 ms |
5116 KB |
correct |
104 |
Correct |
164 ms |
4980 KB |
correct |
105 |
Correct |
165 ms |
5108 KB |
correct |