# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
875874 |
2023-11-20T16:26:14 Z |
Kanon |
Simurgh (IOI17_simurgh) |
C++14 |
|
240 ms |
12204 KB |
#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
class dsu {
public:
vector<int> p;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
inline int get(int x) {
return (x == p[x] ? x : (p[x] = get(p[x])));
}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
return true;
}
return false;
}
};
struct Edge {
int from;
int to;
int cost;
int id;
Edge(){};
Edge(int _from, int _to, int _cost, int _id) : from(_from), to(_to), cost(_cost), id(_id){};
};
struct graph {
int n;
vector<vector<int>> g;
vector<Edge> ed;
vector<bool> was;
graph(int _n) {
n = _n;
g.resize(n);
was.resize(n);
}
void add(int u, int v, int cost = 0) {
g[u].push_back(ed.size());
ed.emplace_back(u, v, cost, ed.size());
g[v].push_back(ed.size());
ed.emplace_back(v, u, -cost, ed.size());
}
void init_dfs() {
fill(was.begin(), was.end(), false);
}
template<typename E, typename F, typename G>
void _dp_dfs(int u, E&& bc, F&& fc, G&& gc) {
was[u] = true;
for(auto &e : g[u]) {
int v = ed[e].to;
if (was[v]) {
bc(u, v, ed[e]);
continue;
}
fc(u, v, ed[e]);
_dp_dfs(v, bc, fc, gc);
gc(u, v, ed[e]);
}
}
const vector<int>& operator[](int u){
return g[u];
}
};
vector<int> find_roads(int n, vector<int> n1, vector<int> n2) {
int m = n1.size();
graph gr(n);
for (int i = 0; i < m; i++) {
gr.add(n1[i], n2[i]);
}
vector<int> cost(m, -2);
graph edges(m);
vector<int> par(n, -1);
vector<int> dep(n);
vector<int> highest(n, -1);
gr._dp_dfs(0,
[&](int u, int v, Edge e) {
if (dep[v] == dep[u] - 1) {
return;
}
if (highest[u] == -1 || dep[gr.ed[highest[u]].to] > dep[v]) {
highest[u] = e.id;
}
},
[&](int u, int v, Edge e) {
par[v] = e.id ^ 1;
dep[v] = dep[u] + 1;
},
[&](int u, int v, Edge e) {
int eu = highest[u], pu = eu == -1 ? u : gr.ed[eu].to;
int ev = highest[v], pv = ev == -1 ? v : gr.ed[ev].to;
if (dep[pu] > dep[pv]) {
highest[u] = ev;
}
}
);
set<int> tree;
for (int i = 1; i < n; i++) {
tree.insert(par[i] >> 1);
}
auto calc = [&](set<int> ed) {
vector<int> que;
for (int i : ed) que.push_back(i);
return count_common_roads(que);
};
int sum = calc(tree);
auto diff = [&](int ev, int eu) {
tree.erase(eu);
tree.insert(ev);
int p = calc(tree);
tree.erase(ev);
tree.insert(eu);
return p - sum;
};
for (int v = 1; v < n; v++) {
int pv = par[v];
int u = gr.ed[pv].to;
int pu = par[u];
int w = highest[v] != -1 ? gr.ed[highest[v]].to : v;
if (dep[w] < dep[v]) {
int d = diff(highest[v] >> 1, pv >> 1);
edges.add(pv >> 1, highest[v] >> 1, d);
}
if (dep[w] < dep[u]) {
int d = diff(highest[v] >> 1, pu >> 1);
edges.add(pu >> 1, highest[v] >> 1, d);
}
}
for (int e : tree) {
if (cost[e] != -2) continue;
if (edges[e].empty()) {
cost[e] = 1;
} else {
vector<int> que = {e};
edges._dp_dfs(e,
[&](int u, int v, Edge E){},
[&](int u, int v, Edge E){
cost[v] = cost[u] + E.cost;
que.push_back(v);
},
[&](int u, int v, Edge E){}
);
int mn = INT_MAX;
for (int i : que) mn = min(mn, cost[i]);
for (int i : que) {
cost[i] -= mn;
assert(0 <= cost[i] && cost[i] <= 1);
}
}
}
auto calc_sum = [&](vector<int> forest) {
dsu d(n);
for (int e : forest) {
e <<= 1;
int u = gr.ed[e].from, v = gr.ed[e].to;
d.unite(u, v);
}
int calced = 0;
for (int e : tree) {
e <<= 1;
int u = gr.ed[e].from, v = gr.ed[e].to;
if (d.unite(u, v)) {
calced += cost[e >> 1];
forest.push_back(e >> 1);
}
}
return count_common_roads(forest) - calced;
};
function<void(vector<int>, int)> solve = [&](vector<int> Eds, int Sum) {
if (Sum == 0) {
for (int e : Eds) {
cost[e] = 0;
}
return;
}
if (Sum == (int) Eds.size()) {
for (int e : Eds) {
cost[e] = 1;
}
return;
}
int L = 0, R = Eds.size(), Mid = (L + R) >> 1;
vector<int> Leds, Reds;
for (int i = 0; i < (int) Eds.size(); i++) {
if (i < Mid) Leds.push_back(Eds[i]);
else Reds.push_back(Eds[i]);
}
int Lsum = calc_sum(Leds), Rsum = Sum - Lsum;
solve(Leds, Lsum);
solve(Reds, Rsum);
};
int Left = 0;
for (int i = 0; i < m; i++) Left += cost[i] == -2;
while (Left) {
dsu d(n);
vector<int> Eds;
for (int e = 0; e < m; e++) {
if (cost[e] != -2) continue;
int u = gr.ed[e << 1].from, v = gr.ed[e << 1].to;
if (d.unite(u, v)) Eds.push_back(e);
}
assert(Eds.size());
solve(Eds, calc_sum(Eds));
Left -= Eds.size();
}
vector<int> ret;
for (int e = 0; e < m; e++) {
assert(0 <= cost[e] && cost[e] <= 1);
if (cost[e] == 1) ret.push_back(e);
}
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
correct |
2 |
Correct |
1 ms |
420 KB |
correct |
3 |
Correct |
1 ms |
348 KB |
correct |
4 |
Correct |
0 ms |
348 KB |
correct |
5 |
Correct |
0 ms |
348 KB |
correct |
6 |
Correct |
0 ms |
436 KB |
correct |
7 |
Correct |
0 ms |
348 KB |
correct |
8 |
Correct |
0 ms |
604 KB |
correct |
9 |
Correct |
1 ms |
348 KB |
correct |
10 |
Correct |
0 ms |
412 KB |
correct |
11 |
Correct |
0 ms |
348 KB |
correct |
12 |
Correct |
0 ms |
348 KB |
correct |
13 |
Correct |
0 ms |
348 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
correct |
2 |
Correct |
1 ms |
420 KB |
correct |
3 |
Correct |
1 ms |
348 KB |
correct |
4 |
Correct |
0 ms |
348 KB |
correct |
5 |
Correct |
0 ms |
348 KB |
correct |
6 |
Correct |
0 ms |
436 KB |
correct |
7 |
Correct |
0 ms |
348 KB |
correct |
8 |
Correct |
0 ms |
604 KB |
correct |
9 |
Correct |
1 ms |
348 KB |
correct |
10 |
Correct |
0 ms |
412 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 |
568 KB |
correct |
16 |
Correct |
2 ms |
348 KB |
correct |
17 |
Correct |
1 ms |
348 KB |
correct |
18 |
Correct |
1 ms |
348 KB |
correct |
19 |
Correct |
1 ms |
444 KB |
correct |
20 |
Correct |
2 ms |
348 KB |
correct |
21 |
Correct |
1 ms |
348 KB |
correct |
22 |
Correct |
1 ms |
348 KB |
correct |
23 |
Correct |
1 ms |
348 KB |
correct |
24 |
Correct |
1 ms |
348 KB |
correct |
25 |
Correct |
1 ms |
600 KB |
correct |
26 |
Correct |
1 ms |
348 KB |
correct |
27 |
Correct |
1 ms |
348 KB |
correct |
28 |
Correct |
1 ms |
348 KB |
correct |
29 |
Correct |
1 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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
correct |
2 |
Correct |
1 ms |
420 KB |
correct |
3 |
Correct |
1 ms |
348 KB |
correct |
4 |
Correct |
0 ms |
348 KB |
correct |
5 |
Correct |
0 ms |
348 KB |
correct |
6 |
Correct |
0 ms |
436 KB |
correct |
7 |
Correct |
0 ms |
348 KB |
correct |
8 |
Correct |
0 ms |
604 KB |
correct |
9 |
Correct |
1 ms |
348 KB |
correct |
10 |
Correct |
0 ms |
412 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 |
568 KB |
correct |
16 |
Correct |
2 ms |
348 KB |
correct |
17 |
Correct |
1 ms |
348 KB |
correct |
18 |
Correct |
1 ms |
348 KB |
correct |
19 |
Correct |
1 ms |
444 KB |
correct |
20 |
Correct |
2 ms |
348 KB |
correct |
21 |
Correct |
1 ms |
348 KB |
correct |
22 |
Correct |
1 ms |
348 KB |
correct |
23 |
Correct |
1 ms |
348 KB |
correct |
24 |
Correct |
1 ms |
348 KB |
correct |
25 |
Correct |
1 ms |
600 KB |
correct |
26 |
Correct |
1 ms |
348 KB |
correct |
27 |
Correct |
1 ms |
348 KB |
correct |
28 |
Correct |
1 ms |
348 KB |
correct |
29 |
Correct |
1 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 |
39 ms |
3216 KB |
correct |
35 |
Correct |
38 ms |
3024 KB |
correct |
36 |
Correct |
30 ms |
2340 KB |
correct |
37 |
Correct |
8 ms |
604 KB |
correct |
38 |
Correct |
39 ms |
3100 KB |
correct |
39 |
Correct |
34 ms |
2768 KB |
correct |
40 |
Correct |
29 ms |
2352 KB |
correct |
41 |
Correct |
42 ms |
3024 KB |
correct |
42 |
Correct |
39 ms |
3024 KB |
correct |
43 |
Correct |
14 ms |
1824 KB |
correct |
44 |
Correct |
12 ms |
1492 KB |
correct |
45 |
Correct |
12 ms |
1748 KB |
correct |
46 |
Correct |
12 ms |
1512 KB |
correct |
47 |
Correct |
8 ms |
860 KB |
correct |
48 |
Correct |
4 ms |
540 KB |
correct |
49 |
Correct |
7 ms |
604 KB |
correct |
50 |
Correct |
10 ms |
1068 KB |
correct |
51 |
Correct |
13 ms |
1748 KB |
correct |
52 |
Correct |
11 ms |
1492 KB |
correct |
53 |
Correct |
11 ms |
1492 KB |
correct |
54 |
Correct |
14 ms |
1988 KB |
correct |
55 |
Correct |
12 ms |
1820 KB |
correct |
56 |
Correct |
12 ms |
1748 KB |
correct |
57 |
Correct |
12 ms |
1748 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
correct |
2 |
Correct |
1 ms |
440 KB |
correct |
3 |
Correct |
129 ms |
8904 KB |
correct |
4 |
Correct |
216 ms |
12204 KB |
correct |
5 |
Correct |
213 ms |
11900 KB |
correct |
6 |
Correct |
231 ms |
11944 KB |
correct |
7 |
Correct |
234 ms |
11964 KB |
correct |
8 |
Correct |
225 ms |
11948 KB |
correct |
9 |
Correct |
214 ms |
11944 KB |
correct |
10 |
Correct |
208 ms |
11956 KB |
correct |
11 |
Correct |
235 ms |
11956 KB |
correct |
12 |
Correct |
206 ms |
11932 KB |
correct |
13 |
Correct |
0 ms |
348 KB |
correct |
14 |
Correct |
209 ms |
11968 KB |
correct |
15 |
Correct |
222 ms |
11964 KB |
correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
correct |
2 |
Correct |
1 ms |
420 KB |
correct |
3 |
Correct |
1 ms |
348 KB |
correct |
4 |
Correct |
0 ms |
348 KB |
correct |
5 |
Correct |
0 ms |
348 KB |
correct |
6 |
Correct |
0 ms |
436 KB |
correct |
7 |
Correct |
0 ms |
348 KB |
correct |
8 |
Correct |
0 ms |
604 KB |
correct |
9 |
Correct |
1 ms |
348 KB |
correct |
10 |
Correct |
0 ms |
412 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 |
568 KB |
correct |
16 |
Correct |
2 ms |
348 KB |
correct |
17 |
Correct |
1 ms |
348 KB |
correct |
18 |
Correct |
1 ms |
348 KB |
correct |
19 |
Correct |
1 ms |
444 KB |
correct |
20 |
Correct |
2 ms |
348 KB |
correct |
21 |
Correct |
1 ms |
348 KB |
correct |
22 |
Correct |
1 ms |
348 KB |
correct |
23 |
Correct |
1 ms |
348 KB |
correct |
24 |
Correct |
1 ms |
348 KB |
correct |
25 |
Correct |
1 ms |
600 KB |
correct |
26 |
Correct |
1 ms |
348 KB |
correct |
27 |
Correct |
1 ms |
348 KB |
correct |
28 |
Correct |
1 ms |
348 KB |
correct |
29 |
Correct |
1 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 |
39 ms |
3216 KB |
correct |
35 |
Correct |
38 ms |
3024 KB |
correct |
36 |
Correct |
30 ms |
2340 KB |
correct |
37 |
Correct |
8 ms |
604 KB |
correct |
38 |
Correct |
39 ms |
3100 KB |
correct |
39 |
Correct |
34 ms |
2768 KB |
correct |
40 |
Correct |
29 ms |
2352 KB |
correct |
41 |
Correct |
42 ms |
3024 KB |
correct |
42 |
Correct |
39 ms |
3024 KB |
correct |
43 |
Correct |
14 ms |
1824 KB |
correct |
44 |
Correct |
12 ms |
1492 KB |
correct |
45 |
Correct |
12 ms |
1748 KB |
correct |
46 |
Correct |
12 ms |
1512 KB |
correct |
47 |
Correct |
8 ms |
860 KB |
correct |
48 |
Correct |
4 ms |
540 KB |
correct |
49 |
Correct |
7 ms |
604 KB |
correct |
50 |
Correct |
10 ms |
1068 KB |
correct |
51 |
Correct |
13 ms |
1748 KB |
correct |
52 |
Correct |
11 ms |
1492 KB |
correct |
53 |
Correct |
11 ms |
1492 KB |
correct |
54 |
Correct |
14 ms |
1988 KB |
correct |
55 |
Correct |
12 ms |
1820 KB |
correct |
56 |
Correct |
12 ms |
1748 KB |
correct |
57 |
Correct |
12 ms |
1748 KB |
correct |
58 |
Correct |
0 ms |
348 KB |
correct |
59 |
Correct |
1 ms |
440 KB |
correct |
60 |
Correct |
129 ms |
8904 KB |
correct |
61 |
Correct |
216 ms |
12204 KB |
correct |
62 |
Correct |
213 ms |
11900 KB |
correct |
63 |
Correct |
231 ms |
11944 KB |
correct |
64 |
Correct |
234 ms |
11964 KB |
correct |
65 |
Correct |
225 ms |
11948 KB |
correct |
66 |
Correct |
214 ms |
11944 KB |
correct |
67 |
Correct |
208 ms |
11956 KB |
correct |
68 |
Correct |
235 ms |
11956 KB |
correct |
69 |
Correct |
206 ms |
11932 KB |
correct |
70 |
Correct |
0 ms |
348 KB |
correct |
71 |
Correct |
209 ms |
11968 KB |
correct |
72 |
Correct |
222 ms |
11964 KB |
correct |
73 |
Correct |
0 ms |
348 KB |
correct |
74 |
Correct |
209 ms |
11944 KB |
correct |
75 |
Correct |
234 ms |
11792 KB |
correct |
76 |
Correct |
81 ms |
4556 KB |
correct |
77 |
Correct |
224 ms |
11876 KB |
correct |
78 |
Correct |
240 ms |
11928 KB |
correct |
79 |
Correct |
236 ms |
11712 KB |
correct |
80 |
Correct |
203 ms |
11456 KB |
correct |
81 |
Correct |
180 ms |
10380 KB |
correct |
82 |
Correct |
230 ms |
11720 KB |
correct |
83 |
Correct |
127 ms |
6368 KB |
correct |
84 |
Correct |
85 ms |
8140 KB |
correct |
85 |
Correct |
73 ms |
6808 KB |
correct |
86 |
Correct |
53 ms |
4760 KB |
correct |
87 |
Correct |
41 ms |
3620 KB |
correct |
88 |
Correct |
34 ms |
2776 KB |
correct |
89 |
Correct |
32 ms |
2768 KB |
correct |
90 |
Correct |
30 ms |
2256 KB |
correct |
91 |
Correct |
19 ms |
856 KB |
correct |
92 |
Correct |
19 ms |
604 KB |
correct |
93 |
Correct |
80 ms |
6764 KB |
correct |
94 |
Correct |
51 ms |
4812 KB |
correct |
95 |
Correct |
47 ms |
4556 KB |
correct |
96 |
Correct |
45 ms |
2512 KB |
correct |
97 |
Correct |
33 ms |
2768 KB |
correct |
98 |
Correct |
37 ms |
3652 KB |
correct |
99 |
Correct |
34 ms |
2768 KB |
correct |
100 |
Correct |
32 ms |
1084 KB |
correct |
101 |
Correct |
23 ms |
688 KB |
correct |
102 |
Correct |
62 ms |
6092 KB |
correct |
103 |
Correct |
62 ms |
6276 KB |
correct |
104 |
Correct |
61 ms |
6248 KB |
correct |
105 |
Correct |
67 ms |
6196 KB |
correct |