#include "simurgh.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 505;
int n, m;
vector<array<int, 2>> g[maxn], tr[maxn];
vector<int> state, te, vis, used, U, V;
void pre(int v) {
vis[v] = 1;
for(auto [i, id] : g[v]) if(!vis[i]) {
pre(i);
used.push_back(id);
te[id] = 1;
tr[v].push_back({i, id});
tr[i].push_back({v, id});
}
}
vector<int> _path;
bool find(int v, int t) {
if(v == t) return true;
vis[v] = 1;
int ok = 0;
for(auto [i, id] : tr[v]) if(!vis[i]) {
if(find(i, t)) _path.push_back(id), ok = 1;
}
return ok;
}
vector<int> find_path(int u, int v) {
_path.clear();
vis.assign(n, 0);
find(u, v);
return _path;
}
int alter(int id, int nid) {
vector<int> t = used;
for(auto &i : t) if(i == id) swap(i, t.back());
t.pop_back();
t.push_back(nid);
int res = count_common_roads(t);
//cout << "====query====\n";
//for(auto i : t) cout << i << " "; cout << " :: " << res << endl;
return res;
}
struct dsu {
vector<int> r, p;
dsu(int n) : r(n), p(n) {iota(p.begin(), p.end(), 0);}
int par(int v) { return v == p[v] ? v : p[v] = par(p[v]); }
void unite(int i, int j) {
i = par(i), j = par(j);
if(i == j) return;
if(r[i] < r[j]) swap(i, j);
p[j] = i;
r[i] += r[j];
}
bool con(int i, int j) {
return par(i) == par(j);
}
};
int count(int v, int p) {
vector<int> t;
dsu d(n);
for(int i = 0; i < p; i++) {
t.push_back(g[v][i][1]);
d.unite(v, g[v][i][0]);
}
int bias = 0;
for(auto i : used) if(!d.con(U[i], V[i])) {
d.unite(U[i], V[i]);
t.push_back(i);
bias += state[i] == 2;
}
bias = count_common_roads(t) - bias;
return bias;
}
std::vector<int> find_roads(int _n, std::vector<int> u, std::vector<int> v) {
for(int i = 0; i < u.size(); i++) g[u[i]].push_back({v[i], i});
for(int i = 0; i < u.size(); i++) g[v[i]].push_back({u[i], i});
U = u, V = v;
n = _n;
m = u.size();
state.resize(m);
te.resize(m);
vis.resize(n);
pre(0);
//cout << "Init tree is ";
//for(auto i : used) cout << u[i] << " " << v[i] << '\n';
int init = count_common_roads(used);
//cout << "init " << init << endl;
for(int i = 0; i < m; i++) if(!te[i]) {
vector<int> t = find_path(u[i], v[i]);
//cout << "Determining " << u[i] << " " << v[i] << endl;
//cout << "Path:\n";
//for(auto i : t) cout << u[i] << " " << v[i] << " | " << i << " " << state[i] << '\n';
int det = 0, unset = 0;
for(auto id : t) unset += state[id] == 0;
if(unset == 0) continue;
for(auto id : t) {
if(state[id]) {
int tmp = alter(id, i);
if(state[id] == 2) det = 1+(tmp == init);
else det = 1+(tmp>init);
break;
}
}
//cout << "det is " << det << '\n';
if(det) {
state[i] = det;
for(auto &id : t) if(!state[id]) {
int tmp = alter(id, i);
if(det == 2) state[id] = 1+(tmp == init);
else state[id] = 1+(tmp<init);
}
continue;
}
vector<int> results;
int mx = init;
for(auto id : t) {
results.push_back(alter(id, i));
mx = max(mx, results.back());
}
//cout << "Here, " << mx << '\n';
for(int i = 0; i < t.size(); i++)
state[t[i]] = 1+(results[i]!=mx);
state[i] = 1+(init!=mx);
}
for(auto i : used) if(!state[i]) state[i] = 2;
for(int i = 0; i < n; i++) {
for(int j = g[i].size(); j--;) {
if(count(used.begin(), used.end(), g[i][j][1]) || g[i][j][0] < i)
swap(g[i][j], g[i].back()), g[i].pop_back();
}
int cnt = count(i, g[i].size()), p = 0;
for(int F = 0; F < cnt; F++) {
for(int z = 1<<9; z>>=1;)
if(p+z <= g[i].size() && count(i, p+z) <= F) p+=z;
state[g[i][p][1]] = 2;
}
}
std::vector<int> r;
//for(int i = 0; i < m; i++) cout << state[i] << " "; cout << '\n';
//cout << "Didn't crash\n";
for(int i = 0; i < m; i++) if(state[i] == 2) r.push_back(i);
//for(auto i : r) cout << i << '\n';
return r;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:77:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < u.size(); i++) g[u[i]].push_back({v[i], i});
~~^~~~~~~~~~
simurgh.cpp:78:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < u.size(); i++) g[v[i]].push_back({u[i], i});
~~^~~~~~~~~~
simurgh.cpp:126:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < t.size(); i++)
~~^~~~~~~~~~
simurgh.cpp:139:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(p+z <= g[i].size() && count(i, p+z) <= F) p+=z;
~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
correct |
2 |
Correct |
0 ms |
384 KB |
correct |
3 |
Correct |
0 ms |
384 KB |
correct |
4 |
Correct |
0 ms |
384 KB |
correct |
5 |
Correct |
1 ms |
384 KB |
correct |
6 |
Correct |
1 ms |
396 KB |
correct |
7 |
Correct |
0 ms |
384 KB |
correct |
8 |
Correct |
0 ms |
384 KB |
correct |
9 |
Correct |
1 ms |
384 KB |
correct |
10 |
Correct |
0 ms |
384 KB |
correct |
11 |
Correct |
0 ms |
384 KB |
correct |
12 |
Correct |
0 ms |
384 KB |
correct |
13 |
Correct |
0 ms |
384 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
correct |
2 |
Correct |
0 ms |
384 KB |
correct |
3 |
Correct |
0 ms |
384 KB |
correct |
4 |
Correct |
0 ms |
384 KB |
correct |
5 |
Correct |
1 ms |
384 KB |
correct |
6 |
Correct |
1 ms |
396 KB |
correct |
7 |
Correct |
0 ms |
384 KB |
correct |
8 |
Correct |
0 ms |
384 KB |
correct |
9 |
Correct |
1 ms |
384 KB |
correct |
10 |
Correct |
0 ms |
384 KB |
correct |
11 |
Correct |
0 ms |
384 KB |
correct |
12 |
Correct |
0 ms |
384 KB |
correct |
13 |
Correct |
0 ms |
384 KB |
correct |
14 |
Correct |
2 ms |
384 KB |
correct |
15 |
Correct |
3 ms |
384 KB |
correct |
16 |
Correct |
2 ms |
384 KB |
correct |
17 |
Correct |
2 ms |
384 KB |
correct |
18 |
Correct |
2 ms |
384 KB |
correct |
19 |
Correct |
2 ms |
384 KB |
correct |
20 |
Correct |
2 ms |
384 KB |
correct |
21 |
Correct |
2 ms |
384 KB |
correct |
22 |
Correct |
2 ms |
384 KB |
correct |
23 |
Correct |
1 ms |
384 KB |
correct |
24 |
Correct |
1 ms |
384 KB |
correct |
25 |
Correct |
1 ms |
384 KB |
correct |
26 |
Correct |
1 ms |
384 KB |
correct |
27 |
Correct |
1 ms |
384 KB |
correct |
28 |
Correct |
1 ms |
384 KB |
correct |
29 |
Correct |
1 ms |
384 KB |
correct |
30 |
Correct |
2 ms |
384 KB |
correct |
31 |
Correct |
1 ms |
384 KB |
correct |
32 |
Correct |
1 ms |
384 KB |
correct |
33 |
Correct |
2 ms |
384 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
correct |
2 |
Correct |
0 ms |
384 KB |
correct |
3 |
Correct |
0 ms |
384 KB |
correct |
4 |
Correct |
0 ms |
384 KB |
correct |
5 |
Correct |
1 ms |
384 KB |
correct |
6 |
Correct |
1 ms |
396 KB |
correct |
7 |
Correct |
0 ms |
384 KB |
correct |
8 |
Correct |
0 ms |
384 KB |
correct |
9 |
Correct |
1 ms |
384 KB |
correct |
10 |
Correct |
0 ms |
384 KB |
correct |
11 |
Correct |
0 ms |
384 KB |
correct |
12 |
Correct |
0 ms |
384 KB |
correct |
13 |
Correct |
0 ms |
384 KB |
correct |
14 |
Correct |
2 ms |
384 KB |
correct |
15 |
Correct |
3 ms |
384 KB |
correct |
16 |
Correct |
2 ms |
384 KB |
correct |
17 |
Correct |
2 ms |
384 KB |
correct |
18 |
Correct |
2 ms |
384 KB |
correct |
19 |
Correct |
2 ms |
384 KB |
correct |
20 |
Correct |
2 ms |
384 KB |
correct |
21 |
Correct |
2 ms |
384 KB |
correct |
22 |
Correct |
2 ms |
384 KB |
correct |
23 |
Correct |
1 ms |
384 KB |
correct |
24 |
Correct |
1 ms |
384 KB |
correct |
25 |
Correct |
1 ms |
384 KB |
correct |
26 |
Correct |
1 ms |
384 KB |
correct |
27 |
Correct |
1 ms |
384 KB |
correct |
28 |
Correct |
1 ms |
384 KB |
correct |
29 |
Correct |
1 ms |
384 KB |
correct |
30 |
Correct |
2 ms |
384 KB |
correct |
31 |
Correct |
1 ms |
384 KB |
correct |
32 |
Correct |
1 ms |
384 KB |
correct |
33 |
Correct |
2 ms |
384 KB |
correct |
34 |
Correct |
106 ms |
1920 KB |
correct |
35 |
Correct |
104 ms |
1920 KB |
correct |
36 |
Correct |
75 ms |
1664 KB |
correct |
37 |
Correct |
14 ms |
384 KB |
correct |
38 |
Correct |
105 ms |
1920 KB |
correct |
39 |
Correct |
91 ms |
1864 KB |
correct |
40 |
Correct |
76 ms |
1664 KB |
correct |
41 |
Correct |
102 ms |
1920 KB |
correct |
42 |
Correct |
110 ms |
2024 KB |
correct |
43 |
Correct |
53 ms |
1408 KB |
correct |
44 |
Correct |
46 ms |
1024 KB |
correct |
45 |
Correct |
53 ms |
1152 KB |
correct |
46 |
Correct |
40 ms |
1024 KB |
correct |
47 |
Correct |
23 ms |
640 KB |
correct |
48 |
Correct |
6 ms |
384 KB |
correct |
49 |
Correct |
12 ms |
384 KB |
correct |
50 |
Correct |
23 ms |
640 KB |
correct |
51 |
Correct |
50 ms |
1152 KB |
correct |
52 |
Correct |
47 ms |
1024 KB |
correct |
53 |
Correct |
40 ms |
1024 KB |
correct |
54 |
Correct |
56 ms |
1408 KB |
correct |
55 |
Correct |
53 ms |
1152 KB |
correct |
56 |
Correct |
54 ms |
1152 KB |
correct |
57 |
Correct |
55 ms |
1152 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
correct |
2 |
Correct |
0 ms |
384 KB |
correct |
3 |
Correct |
443 ms |
5368 KB |
correct |
4 |
Correct |
824 ms |
7544 KB |
correct |
5 |
Correct |
834 ms |
7416 KB |
correct |
6 |
Correct |
822 ms |
7488 KB |
correct |
7 |
Correct |
842 ms |
7544 KB |
correct |
8 |
Correct |
851 ms |
7416 KB |
correct |
9 |
Correct |
852 ms |
7488 KB |
correct |
10 |
Correct |
855 ms |
7488 KB |
correct |
11 |
Correct |
833 ms |
7544 KB |
correct |
12 |
Correct |
867 ms |
7520 KB |
correct |
13 |
Correct |
1 ms |
384 KB |
correct |
14 |
Correct |
854 ms |
7548 KB |
correct |
15 |
Correct |
873 ms |
7544 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
correct |
2 |
Correct |
0 ms |
384 KB |
correct |
3 |
Correct |
0 ms |
384 KB |
correct |
4 |
Correct |
0 ms |
384 KB |
correct |
5 |
Correct |
1 ms |
384 KB |
correct |
6 |
Correct |
1 ms |
396 KB |
correct |
7 |
Correct |
0 ms |
384 KB |
correct |
8 |
Correct |
0 ms |
384 KB |
correct |
9 |
Correct |
1 ms |
384 KB |
correct |
10 |
Correct |
0 ms |
384 KB |
correct |
11 |
Correct |
0 ms |
384 KB |
correct |
12 |
Correct |
0 ms |
384 KB |
correct |
13 |
Correct |
0 ms |
384 KB |
correct |
14 |
Correct |
2 ms |
384 KB |
correct |
15 |
Correct |
3 ms |
384 KB |
correct |
16 |
Correct |
2 ms |
384 KB |
correct |
17 |
Correct |
2 ms |
384 KB |
correct |
18 |
Correct |
2 ms |
384 KB |
correct |
19 |
Correct |
2 ms |
384 KB |
correct |
20 |
Correct |
2 ms |
384 KB |
correct |
21 |
Correct |
2 ms |
384 KB |
correct |
22 |
Correct |
2 ms |
384 KB |
correct |
23 |
Correct |
1 ms |
384 KB |
correct |
24 |
Correct |
1 ms |
384 KB |
correct |
25 |
Correct |
1 ms |
384 KB |
correct |
26 |
Correct |
1 ms |
384 KB |
correct |
27 |
Correct |
1 ms |
384 KB |
correct |
28 |
Correct |
1 ms |
384 KB |
correct |
29 |
Correct |
1 ms |
384 KB |
correct |
30 |
Correct |
2 ms |
384 KB |
correct |
31 |
Correct |
1 ms |
384 KB |
correct |
32 |
Correct |
1 ms |
384 KB |
correct |
33 |
Correct |
2 ms |
384 KB |
correct |
34 |
Correct |
106 ms |
1920 KB |
correct |
35 |
Correct |
104 ms |
1920 KB |
correct |
36 |
Correct |
75 ms |
1664 KB |
correct |
37 |
Correct |
14 ms |
384 KB |
correct |
38 |
Correct |
105 ms |
1920 KB |
correct |
39 |
Correct |
91 ms |
1864 KB |
correct |
40 |
Correct |
76 ms |
1664 KB |
correct |
41 |
Correct |
102 ms |
1920 KB |
correct |
42 |
Correct |
110 ms |
2024 KB |
correct |
43 |
Correct |
53 ms |
1408 KB |
correct |
44 |
Correct |
46 ms |
1024 KB |
correct |
45 |
Correct |
53 ms |
1152 KB |
correct |
46 |
Correct |
40 ms |
1024 KB |
correct |
47 |
Correct |
23 ms |
640 KB |
correct |
48 |
Correct |
6 ms |
384 KB |
correct |
49 |
Correct |
12 ms |
384 KB |
correct |
50 |
Correct |
23 ms |
640 KB |
correct |
51 |
Correct |
50 ms |
1152 KB |
correct |
52 |
Correct |
47 ms |
1024 KB |
correct |
53 |
Correct |
40 ms |
1024 KB |
correct |
54 |
Correct |
56 ms |
1408 KB |
correct |
55 |
Correct |
53 ms |
1152 KB |
correct |
56 |
Correct |
54 ms |
1152 KB |
correct |
57 |
Correct |
55 ms |
1152 KB |
correct |
58 |
Correct |
0 ms |
384 KB |
correct |
59 |
Correct |
0 ms |
384 KB |
correct |
60 |
Correct |
443 ms |
5368 KB |
correct |
61 |
Correct |
824 ms |
7544 KB |
correct |
62 |
Correct |
834 ms |
7416 KB |
correct |
63 |
Correct |
822 ms |
7488 KB |
correct |
64 |
Correct |
842 ms |
7544 KB |
correct |
65 |
Correct |
851 ms |
7416 KB |
correct |
66 |
Correct |
852 ms |
7488 KB |
correct |
67 |
Correct |
855 ms |
7488 KB |
correct |
68 |
Correct |
833 ms |
7544 KB |
correct |
69 |
Correct |
867 ms |
7520 KB |
correct |
70 |
Correct |
1 ms |
384 KB |
correct |
71 |
Correct |
854 ms |
7548 KB |
correct |
72 |
Correct |
873 ms |
7544 KB |
correct |
73 |
Correct |
0 ms |
384 KB |
correct |
74 |
Correct |
828 ms |
7544 KB |
correct |
75 |
Correct |
800 ms |
7416 KB |
correct |
76 |
Correct |
274 ms |
3064 KB |
correct |
77 |
Correct |
837 ms |
7508 KB |
correct |
78 |
Correct |
833 ms |
7544 KB |
correct |
79 |
Correct |
850 ms |
7544 KB |
correct |
80 |
Correct |
785 ms |
7288 KB |
correct |
81 |
Correct |
698 ms |
6520 KB |
correct |
82 |
Correct |
796 ms |
7288 KB |
correct |
83 |
Correct |
459 ms |
4224 KB |
correct |
84 |
Correct |
475 ms |
4984 KB |
correct |
85 |
Correct |
410 ms |
4736 KB |
correct |
86 |
Correct |
283 ms |
3072 KB |
correct |
87 |
Correct |
214 ms |
2636 KB |
correct |
88 |
Correct |
179 ms |
1920 KB |
correct |
89 |
Correct |
168 ms |
1792 KB |
correct |
90 |
Correct |
145 ms |
1664 KB |
correct |
91 |
Correct |
43 ms |
512 KB |
correct |
92 |
Correct |
23 ms |
384 KB |
correct |
93 |
Correct |
395 ms |
4732 KB |
correct |
94 |
Correct |
293 ms |
3168 KB |
correct |
95 |
Correct |
271 ms |
3072 KB |
correct |
96 |
Correct |
165 ms |
1776 KB |
correct |
97 |
Correct |
179 ms |
1920 KB |
correct |
98 |
Correct |
206 ms |
2560 KB |
correct |
99 |
Correct |
197 ms |
2040 KB |
correct |
100 |
Correct |
75 ms |
768 KB |
correct |
101 |
Correct |
24 ms |
504 KB |
correct |
102 |
Correct |
430 ms |
4088 KB |
correct |
103 |
Correct |
444 ms |
3960 KB |
correct |
104 |
Correct |
437 ms |
4088 KB |
correct |
105 |
Correct |
412 ms |
3968 KB |
correct |