// model_solution/split-kostka-full.cpp
#include "bits/stdc++.h"
#include "split.h"
using namespace std;
vector <int> find_split(int n, int a, int b, int c, vector <int> p, vector <int> q) {
vector <pair <int, int> > edges;
for(int i=0; i<(int)p.size(); i++) edges.emplace_back(p[i], q[i]);
vector <pair <int, int> > sizes = {{a,0}, {b,1}, {c,2}};
sort(sizes.begin(), sizes.end());
a = sizes[0].first; b = sizes[1].first; c = sizes[2].first;
vector <int> rep(n), siz(n);
for(int i=0; i<n; i++) {
rep[i] = i;
siz[i] = 1;
}
function <int(int)> find = [&](int x) {
if(rep[x] == x) return x;
return rep[x] = find(rep[x]);
};
auto unia = [&](int aa, int bb) -> bool {
int fa = find(aa), fb = find(bb);
if(fa == fb) return false;
if(siz[fa] < siz[fb]) swap(fa, fb);
siz[fa] += siz[fb];
rep[fb] = fa;
return true;
};
vector <vector <int> > G(n);
vector <pair <int, int> > non_tree;
for(auto edge : edges) {
if(unia(edge.first, edge.second)) {
G[edge.first].push_back(edge.second);
G[edge.second].push_back(edge.first);
} else {
non_tree.push_back(edge);
}
}
vector <bool> vis(n);
vector <int> subtree(n);
function<void(int)> dfs1 = [&](int v) {
vis[v] = true;
subtree[v] = 1;
for(auto w : G[v]) if(!vis[w]) {
dfs1(w);
subtree[v] += subtree[w];
}
};
dfs1(0);
vis = vector<bool>(n, false);
pair <int, int> both_dir = {-1, -1};
vector <pair <int, int> > dir;
function<void(int)> dfs2 = [&](int v) {
vis[v] = true;
for(auto w : G[v]) if(!vis[w]) {
int below = subtree[w], above = n - subtree[w];
if(min(below, above) >= a) {
if(above < below) both_dir = {v, w};
else both_dir = {w, v};
}
else {
if(below < a) dir.emplace_back(v, w);
else if(above < a) dir.emplace_back(w, v);
}
dfs2(w);
}
};
dfs2(0);
auto find_solution = [&](int pa, int pb) -> vector<int> {
vector <int> ret(n, -1);
int counter;
function<void(int, int)> dfs3 = [&](int v, int mark) {
if(counter == 0) return;
--counter;
ret[v] = mark;
for(auto w : G[v]) if(ret[w] == -1) dfs3(w, mark);
};
ret[pa] = sizes[0].second;
ret[pb] = sizes[a].second;
counter = a;
dfs3(pa, sizes[0].second);
vis[pb] = sizes[1].second;
counter = b;
dfs3(pb, sizes[1].second);
vis[pa] = false;
for(int i=0; i<n; i++) if(ret[i] == -1) ret[i] = sizes[2].second;
for(int i=0; i<n; i++) ret[i]++;
return ret;
};
if(both_dir.first != -1) {
return find_solution(both_dir.first, both_dir.second);
} else {
vector <int> in_deg(n);
for(auto edge : dir) in_deg[edge.second]++;
vector <int> CH;
for(int i=0; i<n; i++) if(in_deg[i] == 0) CH.push_back(i);
assert((int)CH.size() == 1);
vis = vector<bool>(n, false);
subtree = vector<int>(n, 0);
int root = CH.back();
for(auto edge : non_tree) {
G[edge.first].push_back(edge.second);
G[edge.second].push_back(edge.first);
}
dfs1(root);
for(auto son : G[root]) {
if(subtree[son] >= a) return find_solution(son, root);
}
return vector<int>(n, 0);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
ok, correct split |
2 |
Correct |
2 ms |
256 KB |
ok, correct split |
3 |
Correct |
2 ms |
376 KB |
ok, correct split |
4 |
Correct |
2 ms |
376 KB |
ok, correct split |
5 |
Correct |
2 ms |
256 KB |
ok, correct split |
6 |
Correct |
2 ms |
256 KB |
ok, correct split |
7 |
Correct |
113 ms |
18284 KB |
ok, correct split |
8 |
Correct |
115 ms |
14940 KB |
ok, correct split |
9 |
Correct |
117 ms |
14160 KB |
ok, correct split |
10 |
Correct |
124 ms |
17260 KB |
ok, correct split |
11 |
Correct |
116 ms |
17232 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
ok, correct split |
2 |
Correct |
2 ms |
376 KB |
ok, correct split |
3 |
Correct |
2 ms |
376 KB |
ok, correct split |
4 |
Correct |
120 ms |
11560 KB |
ok, correct split |
5 |
Correct |
99 ms |
9836 KB |
ok, correct split |
6 |
Correct |
112 ms |
17472 KB |
ok, correct split |
7 |
Correct |
125 ms |
14672 KB |
ok, correct split |
8 |
Correct |
134 ms |
12760 KB |
ok, correct split |
9 |
Correct |
102 ms |
9836 KB |
ok, correct split |
10 |
Correct |
72 ms |
10220 KB |
ok, correct split |
11 |
Correct |
73 ms |
10092 KB |
ok, correct split |
12 |
Correct |
74 ms |
10092 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
ok, correct split |
2 |
Correct |
102 ms |
11068 KB |
ok, correct split |
3 |
Correct |
37 ms |
4720 KB |
ok, correct split |
4 |
Correct |
2 ms |
376 KB |
ok, correct split |
5 |
Correct |
117 ms |
13548 KB |
ok, correct split |
6 |
Correct |
139 ms |
13196 KB |
ok, correct split |
7 |
Correct |
112 ms |
13036 KB |
ok, correct split |
8 |
Correct |
122 ms |
14044 KB |
ok, correct split |
9 |
Correct |
118 ms |
12880 KB |
ok, correct split |
10 |
Correct |
33 ms |
4080 KB |
ok, no valid answer |
11 |
Correct |
48 ms |
5748 KB |
ok, no valid answer |
12 |
Correct |
87 ms |
11252 KB |
ok, no valid answer |
13 |
Correct |
99 ms |
11096 KB |
ok, no valid answer |
14 |
Correct |
76 ms |
11376 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
ok, correct split |
2 |
Correct |
2 ms |
376 KB |
ok, no valid answer |
3 |
Correct |
2 ms |
256 KB |
ok, correct split |
4 |
Correct |
2 ms |
256 KB |
ok, correct split |
5 |
Correct |
2 ms |
256 KB |
ok, correct split |
6 |
Correct |
2 ms |
256 KB |
ok, correct split |
7 |
Correct |
2 ms |
376 KB |
ok, correct split |
8 |
Correct |
2 ms |
376 KB |
ok, correct split |
9 |
Correct |
4 ms |
632 KB |
ok, correct split |
10 |
Correct |
5 ms |
632 KB |
ok, correct split |
11 |
Correct |
2 ms |
380 KB |
ok, correct split |
12 |
Correct |
5 ms |
760 KB |
ok, correct split |
13 |
Correct |
2 ms |
376 KB |
ok, correct split |
14 |
Correct |
2 ms |
256 KB |
ok, correct split |
15 |
Correct |
2 ms |
376 KB |
ok, correct split |
16 |
Correct |
2 ms |
252 KB |
ok, correct split |
17 |
Correct |
2 ms |
292 KB |
ok, correct split |
18 |
Correct |
2 ms |
376 KB |
ok, correct split |
19 |
Correct |
3 ms |
376 KB |
ok, correct split |
20 |
Correct |
3 ms |
504 KB |
ok, correct split |
21 |
Correct |
4 ms |
632 KB |
ok, correct split |
22 |
Correct |
4 ms |
632 KB |
ok, correct split |
23 |
Correct |
4 ms |
732 KB |
ok, correct split |
24 |
Correct |
4 ms |
632 KB |
ok, correct split |
25 |
Correct |
4 ms |
632 KB |
ok, correct split |
26 |
Correct |
4 ms |
760 KB |
ok, correct split |
27 |
Correct |
4 ms |
760 KB |
ok, correct split |
28 |
Correct |
4 ms |
632 KB |
ok, correct split |
29 |
Correct |
2 ms |
376 KB |
ok, correct split |
30 |
Correct |
4 ms |
636 KB |
ok, correct split |
31 |
Correct |
3 ms |
504 KB |
ok, correct split |
32 |
Correct |
2 ms |
376 KB |
ok, correct split |
33 |
Correct |
2 ms |
376 KB |
ok, correct split |
34 |
Correct |
4 ms |
632 KB |
ok, correct split |
35 |
Correct |
4 ms |
632 KB |
ok, correct split |
36 |
Correct |
4 ms |
632 KB |
ok, correct split |
37 |
Correct |
5 ms |
760 KB |
ok, correct split |
38 |
Correct |
5 ms |
760 KB |
ok, correct split |
39 |
Correct |
5 ms |
632 KB |
ok, correct split |
40 |
Correct |
5 ms |
760 KB |
ok, correct split |
41 |
Correct |
3 ms |
508 KB |
ok, correct split |
42 |
Correct |
3 ms |
504 KB |
ok, correct split |
43 |
Correct |
4 ms |
632 KB |
ok, correct split |
44 |
Correct |
4 ms |
760 KB |
ok, correct split |
45 |
Correct |
4 ms |
760 KB |
ok, correct split |
46 |
Correct |
4 ms |
632 KB |
ok, correct split |
47 |
Correct |
4 ms |
632 KB |
ok, no valid answer |
48 |
Correct |
4 ms |
632 KB |
ok, correct split |
49 |
Correct |
4 ms |
632 KB |
ok, correct split |
50 |
Correct |
2 ms |
376 KB |
ok, no valid answer |
51 |
Correct |
2 ms |
256 KB |
ok, no valid answer |
52 |
Correct |
4 ms |
632 KB |
ok, no valid answer |
53 |
Correct |
5 ms |
632 KB |
ok, no valid answer |
54 |
Correct |
4 ms |
636 KB |
ok, no valid answer |
55 |
Correct |
4 ms |
632 KB |
ok, no valid answer |
56 |
Correct |
5 ms |
632 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
ok, correct split |
2 |
Correct |
2 ms |
256 KB |
ok, correct split |
3 |
Correct |
2 ms |
376 KB |
ok, correct split |
4 |
Correct |
2 ms |
376 KB |
ok, correct split |
5 |
Correct |
2 ms |
256 KB |
ok, correct split |
6 |
Correct |
2 ms |
256 KB |
ok, correct split |
7 |
Correct |
113 ms |
18284 KB |
ok, correct split |
8 |
Correct |
115 ms |
14940 KB |
ok, correct split |
9 |
Correct |
117 ms |
14160 KB |
ok, correct split |
10 |
Correct |
124 ms |
17260 KB |
ok, correct split |
11 |
Correct |
116 ms |
17232 KB |
ok, correct split |
12 |
Correct |
2 ms |
376 KB |
ok, correct split |
13 |
Correct |
2 ms |
376 KB |
ok, correct split |
14 |
Correct |
2 ms |
376 KB |
ok, correct split |
15 |
Correct |
120 ms |
11560 KB |
ok, correct split |
16 |
Correct |
99 ms |
9836 KB |
ok, correct split |
17 |
Correct |
112 ms |
17472 KB |
ok, correct split |
18 |
Correct |
125 ms |
14672 KB |
ok, correct split |
19 |
Correct |
134 ms |
12760 KB |
ok, correct split |
20 |
Correct |
102 ms |
9836 KB |
ok, correct split |
21 |
Correct |
72 ms |
10220 KB |
ok, correct split |
22 |
Correct |
73 ms |
10092 KB |
ok, correct split |
23 |
Correct |
74 ms |
10092 KB |
ok, correct split |
24 |
Correct |
2 ms |
256 KB |
ok, correct split |
25 |
Correct |
102 ms |
11068 KB |
ok, correct split |
26 |
Correct |
37 ms |
4720 KB |
ok, correct split |
27 |
Correct |
2 ms |
376 KB |
ok, correct split |
28 |
Correct |
117 ms |
13548 KB |
ok, correct split |
29 |
Correct |
139 ms |
13196 KB |
ok, correct split |
30 |
Correct |
112 ms |
13036 KB |
ok, correct split |
31 |
Correct |
122 ms |
14044 KB |
ok, correct split |
32 |
Correct |
118 ms |
12880 KB |
ok, correct split |
33 |
Correct |
33 ms |
4080 KB |
ok, no valid answer |
34 |
Correct |
48 ms |
5748 KB |
ok, no valid answer |
35 |
Correct |
87 ms |
11252 KB |
ok, no valid answer |
36 |
Correct |
99 ms |
11096 KB |
ok, no valid answer |
37 |
Correct |
76 ms |
11376 KB |
ok, no valid answer |
38 |
Correct |
2 ms |
256 KB |
ok, correct split |
39 |
Correct |
2 ms |
376 KB |
ok, no valid answer |
40 |
Correct |
2 ms |
256 KB |
ok, correct split |
41 |
Correct |
2 ms |
256 KB |
ok, correct split |
42 |
Correct |
2 ms |
256 KB |
ok, correct split |
43 |
Correct |
2 ms |
256 KB |
ok, correct split |
44 |
Correct |
2 ms |
376 KB |
ok, correct split |
45 |
Correct |
2 ms |
376 KB |
ok, correct split |
46 |
Correct |
4 ms |
632 KB |
ok, correct split |
47 |
Correct |
5 ms |
632 KB |
ok, correct split |
48 |
Correct |
2 ms |
380 KB |
ok, correct split |
49 |
Correct |
5 ms |
760 KB |
ok, correct split |
50 |
Correct |
2 ms |
376 KB |
ok, correct split |
51 |
Correct |
2 ms |
256 KB |
ok, correct split |
52 |
Correct |
2 ms |
376 KB |
ok, correct split |
53 |
Correct |
2 ms |
252 KB |
ok, correct split |
54 |
Correct |
2 ms |
292 KB |
ok, correct split |
55 |
Correct |
2 ms |
376 KB |
ok, correct split |
56 |
Correct |
3 ms |
376 KB |
ok, correct split |
57 |
Correct |
3 ms |
504 KB |
ok, correct split |
58 |
Correct |
4 ms |
632 KB |
ok, correct split |
59 |
Correct |
4 ms |
632 KB |
ok, correct split |
60 |
Correct |
4 ms |
732 KB |
ok, correct split |
61 |
Correct |
4 ms |
632 KB |
ok, correct split |
62 |
Correct |
4 ms |
632 KB |
ok, correct split |
63 |
Correct |
4 ms |
760 KB |
ok, correct split |
64 |
Correct |
4 ms |
760 KB |
ok, correct split |
65 |
Correct |
4 ms |
632 KB |
ok, correct split |
66 |
Correct |
2 ms |
376 KB |
ok, correct split |
67 |
Correct |
4 ms |
636 KB |
ok, correct split |
68 |
Correct |
3 ms |
504 KB |
ok, correct split |
69 |
Correct |
2 ms |
376 KB |
ok, correct split |
70 |
Correct |
2 ms |
376 KB |
ok, correct split |
71 |
Correct |
4 ms |
632 KB |
ok, correct split |
72 |
Correct |
4 ms |
632 KB |
ok, correct split |
73 |
Correct |
4 ms |
632 KB |
ok, correct split |
74 |
Correct |
5 ms |
760 KB |
ok, correct split |
75 |
Correct |
5 ms |
760 KB |
ok, correct split |
76 |
Correct |
5 ms |
632 KB |
ok, correct split |
77 |
Correct |
5 ms |
760 KB |
ok, correct split |
78 |
Correct |
3 ms |
508 KB |
ok, correct split |
79 |
Correct |
3 ms |
504 KB |
ok, correct split |
80 |
Correct |
4 ms |
632 KB |
ok, correct split |
81 |
Correct |
4 ms |
760 KB |
ok, correct split |
82 |
Correct |
4 ms |
760 KB |
ok, correct split |
83 |
Correct |
4 ms |
632 KB |
ok, correct split |
84 |
Correct |
4 ms |
632 KB |
ok, no valid answer |
85 |
Correct |
4 ms |
632 KB |
ok, correct split |
86 |
Correct |
4 ms |
632 KB |
ok, correct split |
87 |
Correct |
2 ms |
376 KB |
ok, no valid answer |
88 |
Correct |
2 ms |
256 KB |
ok, no valid answer |
89 |
Correct |
4 ms |
632 KB |
ok, no valid answer |
90 |
Correct |
5 ms |
632 KB |
ok, no valid answer |
91 |
Correct |
4 ms |
636 KB |
ok, no valid answer |
92 |
Correct |
4 ms |
632 KB |
ok, no valid answer |
93 |
Correct |
5 ms |
632 KB |
ok, no valid answer |
94 |
Correct |
110 ms |
11604 KB |
ok, correct split |
95 |
Correct |
149 ms |
14400 KB |
ok, correct split |
96 |
Correct |
173 ms |
17324 KB |
ok, correct split |
97 |
Correct |
40 ms |
4468 KB |
ok, correct split |
98 |
Correct |
43 ms |
4848 KB |
ok, correct split |
99 |
Correct |
52 ms |
5996 KB |
ok, correct split |
100 |
Correct |
133 ms |
14464 KB |
ok, correct split |
101 |
Correct |
127 ms |
13592 KB |
ok, correct split |
102 |
Correct |
131 ms |
14136 KB |
ok, correct split |
103 |
Correct |
119 ms |
13672 KB |
ok, correct split |
104 |
Correct |
114 ms |
15224 KB |
ok, correct split |
105 |
Correct |
64 ms |
7052 KB |
ok, correct split |
106 |
Correct |
107 ms |
14852 KB |
ok, correct split |
107 |
Correct |
146 ms |
10988 KB |
ok, correct split |
108 |
Correct |
98 ms |
10988 KB |
ok, correct split |
109 |
Correct |
135 ms |
14056 KB |
ok, correct split |
110 |
Correct |
157 ms |
14952 KB |
ok, correct split |
111 |
Correct |
156 ms |
15196 KB |
ok, correct split |
112 |
Correct |
193 ms |
15336 KB |
ok, correct split |
113 |
Correct |
160 ms |
15568 KB |
ok, correct split |
114 |
Correct |
16 ms |
2164 KB |
ok, correct split |
115 |
Correct |
16 ms |
1908 KB |
ok, correct split |
116 |
Correct |
128 ms |
14620 KB |
ok, correct split |
117 |
Correct |
132 ms |
14440 KB |
ok, correct split |
118 |
Correct |
104 ms |
10988 KB |
ok, correct split |
119 |
Correct |
123 ms |
11124 KB |
ok, correct split |
120 |
Correct |
125 ms |
14032 KB |
ok, correct split |
121 |
Correct |
106 ms |
11376 KB |
ok, no valid answer |
122 |
Correct |
104 ms |
11248 KB |
ok, no valid answer |
123 |
Correct |
167 ms |
15592 KB |
ok, no valid answer |
124 |
Correct |
159 ms |
15464 KB |
ok, no valid answer |
125 |
Correct |
105 ms |
12656 KB |
ok, no valid answer |
126 |
Correct |
76 ms |
10348 KB |
ok, no valid answer |
127 |
Correct |
110 ms |
13672 KB |
ok, no valid answer |