// moreflags=grader.cpp
// not my solution. :(
#include "split.h"
#include<array>
#if not LOCAL
#define NDEBUG
#endif
#include<algorithm>
#include<cassert>
struct Dsu{
std::vector<int> data; // data = parent if positive, -subtreeSize if negative
Dsu(int number){reset(number);}
void reset(int number){
data.assign(number, -1);
}
int root(int node){return data[node]>=0 ? data[node]=root(data[node]): node;}
bool join(int first, int sec){
first=root(first); sec=root(sec);
if(first==sec) return false;
data[sec]+=data[first];
data[first]=sec;
return true;
}
};
std::vector<std::vector<int>> add;
int work(int node, int par){
int subtreeSize=1;
int maxChild=0;
for(auto child: add[node]) if(child!=par){
int const tmp=work(child, node);
maxChild=std::max(maxChild, tmp);
subtreeSize+=tmp;
}
if(std::max((int)add.size()-subtreeSize, maxChild)*2<=(int)add.size())
throw node;
return subtreeSize;
}
std::vector<int> find_split(int n, int a, int b, int c, std::vector<int> p, std::vector<int> q) {
add.clear(); add.resize(n);
std::array<std::pair<int, int>, 3> sizes{{{a, 1}, {b, 2}, {c, 3}}};
std::sort(begin(sizes), end(sizes));
a=b=c=-1;
Dsu dsu(n);
for(int index=0; index<(int)p.size(); ++index){
auto const first=p[index], sec=q[index];
if(dsu.join(first, sec)){
add[first].push_back(sec); add[sec].push_back(first);
}
}
try{
work(0, -1);
}catch(int centroid){
dsu.reset(n);
auto const process=[&](int root)->std::vector<int>{
assert(root!=centroid);
assert(dsu.data[root]<0 and -dsu.data[root]>=sizes[0].first);
assert(std::is_sorted(begin(sizes), end(sizes)));
for(auto& it: add) it.clear();
for(int index=0; index<(int)p.size(); ++index){
auto const first=p[index], sec=q[index];
add[first].push_back(sec); add[sec].push_back(first);
}
std::vector<int> result(n, sizes[2].second);
auto const process=[&](std::pair<int, int> const item, int const startNode, auto condition){
auto const [size, componentId]=item;
std::vector<int> queue;
assert(result[startNode]==sizes[2].second); result[startNode]=componentId;
if(size==1) return;
queue.push_back(startNode);
assert(condition(startNode));
for(int start=0;;++start){
auto const node=queue[start];
for(auto other: add[node]) if(result[other]!=componentId and condition(other)){
assert(result[other]==sizes[2].second); result[other]=componentId;
queue.push_back(other);
if((int)queue.size()==size) return;
}
}
};
process(sizes[0], root, [&](int node){return dsu.root(node)==root;});
process(sizes[1], centroid, [&](int node){return dsu.root(node)!=root;});
return result;
};
for(int node=0; node<n; ++node)
for(auto other: add[node]) if(node!=centroid and other!=centroid)
dsu.join(node, other);
for(int root=0; root<n; ++root)
if(root!=centroid and dsu.data[root]<0 and -dsu.data[root]>=sizes[0].first)
return process(root);
for(int index=0; index<(int)p.size(); ++index){
auto const first=p[index], sec=q[index];
if(first!=centroid and sec!=centroid and dsu.join(first, sec)){
auto const root=dsu.root(first);
if(-dsu.data[root]>=sizes[0].first){
return process(root);
}
}
}
return std::vector<int>(n, 0);
}
assert(false); __builtin_unreachable();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
ok, correct split |
2 |
Correct |
1 ms |
256 KB |
ok, correct split |
3 |
Correct |
1 ms |
256 KB |
ok, correct split |
4 |
Correct |
1 ms |
384 KB |
ok, correct split |
5 |
Correct |
1 ms |
384 KB |
ok, correct split |
6 |
Correct |
1 ms |
384 KB |
ok, correct split |
7 |
Correct |
166 ms |
15608 KB |
ok, correct split |
8 |
Correct |
126 ms |
13560 KB |
ok, correct split |
9 |
Correct |
131 ms |
13304 KB |
ok, correct split |
10 |
Correct |
154 ms |
15356 KB |
ok, correct split |
11 |
Correct |
149 ms |
14712 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
ok, correct split |
2 |
Correct |
1 ms |
256 KB |
ok, correct split |
3 |
Correct |
1 ms |
256 KB |
ok, correct split |
4 |
Correct |
146 ms |
11312 KB |
ok, correct split |
5 |
Correct |
104 ms |
9848 KB |
ok, correct split |
6 |
Correct |
147 ms |
15352 KB |
ok, correct split |
7 |
Correct |
131 ms |
13688 KB |
ok, correct split |
8 |
Correct |
162 ms |
13304 KB |
ok, correct split |
9 |
Correct |
119 ms |
9720 KB |
ok, correct split |
10 |
Correct |
65 ms |
9840 KB |
ok, correct split |
11 |
Correct |
68 ms |
9968 KB |
ok, correct split |
12 |
Correct |
68 ms |
10096 KB |
ok, correct split |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
ok, correct split |
2 |
Correct |
116 ms |
8676 KB |
ok, correct split |
3 |
Correct |
33 ms |
3584 KB |
ok, correct split |
4 |
Correct |
1 ms |
256 KB |
ok, correct split |
5 |
Correct |
133 ms |
10628 KB |
ok, correct split |
6 |
Correct |
125 ms |
10516 KB |
ok, correct split |
7 |
Correct |
132 ms |
10492 KB |
ok, correct split |
8 |
Correct |
138 ms |
11392 KB |
ok, correct split |
9 |
Correct |
131 ms |
10108 KB |
ok, correct split |
10 |
Correct |
27 ms |
2944 KB |
ok, no valid answer |
11 |
Correct |
40 ms |
4352 KB |
ok, no valid answer |
12 |
Correct |
83 ms |
8564 KB |
ok, no valid answer |
13 |
Correct |
100 ms |
8312 KB |
ok, no valid answer |
14 |
Correct |
66 ms |
8560 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
ok, correct split |
2 |
Correct |
1 ms |
256 KB |
ok, no valid answer |
3 |
Correct |
2 ms |
256 KB |
ok, correct split |
4 |
Correct |
1 ms |
384 KB |
ok, correct split |
5 |
Correct |
1 ms |
384 KB |
ok, correct split |
6 |
Correct |
1 ms |
256 KB |
ok, correct split |
7 |
Correct |
1 ms |
256 KB |
ok, correct split |
8 |
Correct |
1 ms |
384 KB |
ok, correct split |
9 |
Correct |
3 ms |
640 KB |
ok, correct split |
10 |
Correct |
4 ms |
640 KB |
ok, correct split |
11 |
Correct |
2 ms |
384 KB |
ok, correct split |
12 |
Correct |
3 ms |
640 KB |
ok, correct split |
13 |
Correct |
1 ms |
256 KB |
ok, correct split |
14 |
Correct |
1 ms |
384 KB |
ok, correct split |
15 |
Correct |
1 ms |
256 KB |
ok, correct split |
16 |
Correct |
1 ms |
384 KB |
ok, correct split |
17 |
Correct |
1 ms |
384 KB |
ok, correct split |
18 |
Correct |
1 ms |
256 KB |
ok, correct split |
19 |
Correct |
1 ms |
384 KB |
ok, correct split |
20 |
Correct |
2 ms |
384 KB |
ok, correct split |
21 |
Correct |
3 ms |
640 KB |
ok, correct split |
22 |
Correct |
3 ms |
640 KB |
ok, correct split |
23 |
Correct |
3 ms |
640 KB |
ok, correct split |
24 |
Correct |
3 ms |
640 KB |
ok, correct split |
25 |
Correct |
3 ms |
640 KB |
ok, correct split |
26 |
Correct |
3 ms |
640 KB |
ok, correct split |
27 |
Correct |
4 ms |
640 KB |
ok, correct split |
28 |
Correct |
3 ms |
640 KB |
ok, correct split |
29 |
Correct |
2 ms |
384 KB |
ok, correct split |
30 |
Correct |
3 ms |
640 KB |
ok, correct split |
31 |
Correct |
2 ms |
384 KB |
ok, correct split |
32 |
Correct |
1 ms |
384 KB |
ok, correct split |
33 |
Correct |
1 ms |
384 KB |
ok, correct split |
34 |
Correct |
3 ms |
640 KB |
ok, correct split |
35 |
Correct |
3 ms |
640 KB |
ok, correct split |
36 |
Correct |
3 ms |
512 KB |
ok, correct split |
37 |
Correct |
4 ms |
640 KB |
ok, correct split |
38 |
Correct |
4 ms |
640 KB |
ok, correct split |
39 |
Correct |
4 ms |
640 KB |
ok, correct split |
40 |
Correct |
4 ms |
640 KB |
ok, correct split |
41 |
Correct |
2 ms |
512 KB |
ok, correct split |
42 |
Correct |
2 ms |
512 KB |
ok, correct split |
43 |
Correct |
3 ms |
640 KB |
ok, correct split |
44 |
Correct |
4 ms |
640 KB |
ok, correct split |
45 |
Correct |
4 ms |
640 KB |
ok, correct split |
46 |
Correct |
4 ms |
640 KB |
ok, correct split |
47 |
Correct |
3 ms |
640 KB |
ok, no valid answer |
48 |
Correct |
3 ms |
512 KB |
ok, correct split |
49 |
Correct |
3 ms |
640 KB |
ok, correct split |
50 |
Correct |
1 ms |
256 KB |
ok, no valid answer |
51 |
Correct |
1 ms |
256 KB |
ok, no valid answer |
52 |
Correct |
3 ms |
512 KB |
ok, no valid answer |
53 |
Correct |
3 ms |
640 KB |
ok, no valid answer |
54 |
Correct |
2 ms |
512 KB |
ok, no valid answer |
55 |
Correct |
3 ms |
640 KB |
ok, no valid answer |
56 |
Correct |
4 ms |
640 KB |
ok, no valid answer |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
ok, correct split |
2 |
Correct |
1 ms |
256 KB |
ok, correct split |
3 |
Correct |
1 ms |
256 KB |
ok, correct split |
4 |
Correct |
1 ms |
384 KB |
ok, correct split |
5 |
Correct |
1 ms |
384 KB |
ok, correct split |
6 |
Correct |
1 ms |
384 KB |
ok, correct split |
7 |
Correct |
166 ms |
15608 KB |
ok, correct split |
8 |
Correct |
126 ms |
13560 KB |
ok, correct split |
9 |
Correct |
131 ms |
13304 KB |
ok, correct split |
10 |
Correct |
154 ms |
15356 KB |
ok, correct split |
11 |
Correct |
149 ms |
14712 KB |
ok, correct split |
12 |
Correct |
1 ms |
384 KB |
ok, correct split |
13 |
Correct |
1 ms |
256 KB |
ok, correct split |
14 |
Correct |
1 ms |
256 KB |
ok, correct split |
15 |
Correct |
146 ms |
11312 KB |
ok, correct split |
16 |
Correct |
104 ms |
9848 KB |
ok, correct split |
17 |
Correct |
147 ms |
15352 KB |
ok, correct split |
18 |
Correct |
131 ms |
13688 KB |
ok, correct split |
19 |
Correct |
162 ms |
13304 KB |
ok, correct split |
20 |
Correct |
119 ms |
9720 KB |
ok, correct split |
21 |
Correct |
65 ms |
9840 KB |
ok, correct split |
22 |
Correct |
68 ms |
9968 KB |
ok, correct split |
23 |
Correct |
68 ms |
10096 KB |
ok, correct split |
24 |
Correct |
1 ms |
256 KB |
ok, correct split |
25 |
Correct |
116 ms |
8676 KB |
ok, correct split |
26 |
Correct |
33 ms |
3584 KB |
ok, correct split |
27 |
Correct |
1 ms |
256 KB |
ok, correct split |
28 |
Correct |
133 ms |
10628 KB |
ok, correct split |
29 |
Correct |
125 ms |
10516 KB |
ok, correct split |
30 |
Correct |
132 ms |
10492 KB |
ok, correct split |
31 |
Correct |
138 ms |
11392 KB |
ok, correct split |
32 |
Correct |
131 ms |
10108 KB |
ok, correct split |
33 |
Correct |
27 ms |
2944 KB |
ok, no valid answer |
34 |
Correct |
40 ms |
4352 KB |
ok, no valid answer |
35 |
Correct |
83 ms |
8564 KB |
ok, no valid answer |
36 |
Correct |
100 ms |
8312 KB |
ok, no valid answer |
37 |
Correct |
66 ms |
8560 KB |
ok, no valid answer |
38 |
Correct |
1 ms |
256 KB |
ok, correct split |
39 |
Correct |
1 ms |
256 KB |
ok, no valid answer |
40 |
Correct |
2 ms |
256 KB |
ok, correct split |
41 |
Correct |
1 ms |
384 KB |
ok, correct split |
42 |
Correct |
1 ms |
384 KB |
ok, correct split |
43 |
Correct |
1 ms |
256 KB |
ok, correct split |
44 |
Correct |
1 ms |
256 KB |
ok, correct split |
45 |
Correct |
1 ms |
384 KB |
ok, correct split |
46 |
Correct |
3 ms |
640 KB |
ok, correct split |
47 |
Correct |
4 ms |
640 KB |
ok, correct split |
48 |
Correct |
2 ms |
384 KB |
ok, correct split |
49 |
Correct |
3 ms |
640 KB |
ok, correct split |
50 |
Correct |
1 ms |
256 KB |
ok, correct split |
51 |
Correct |
1 ms |
384 KB |
ok, correct split |
52 |
Correct |
1 ms |
256 KB |
ok, correct split |
53 |
Correct |
1 ms |
384 KB |
ok, correct split |
54 |
Correct |
1 ms |
384 KB |
ok, correct split |
55 |
Correct |
1 ms |
256 KB |
ok, correct split |
56 |
Correct |
1 ms |
384 KB |
ok, correct split |
57 |
Correct |
2 ms |
384 KB |
ok, correct split |
58 |
Correct |
3 ms |
640 KB |
ok, correct split |
59 |
Correct |
3 ms |
640 KB |
ok, correct split |
60 |
Correct |
3 ms |
640 KB |
ok, correct split |
61 |
Correct |
3 ms |
640 KB |
ok, correct split |
62 |
Correct |
3 ms |
640 KB |
ok, correct split |
63 |
Correct |
3 ms |
640 KB |
ok, correct split |
64 |
Correct |
4 ms |
640 KB |
ok, correct split |
65 |
Correct |
3 ms |
640 KB |
ok, correct split |
66 |
Correct |
2 ms |
384 KB |
ok, correct split |
67 |
Correct |
3 ms |
640 KB |
ok, correct split |
68 |
Correct |
2 ms |
384 KB |
ok, correct split |
69 |
Correct |
1 ms |
384 KB |
ok, correct split |
70 |
Correct |
1 ms |
384 KB |
ok, correct split |
71 |
Correct |
3 ms |
640 KB |
ok, correct split |
72 |
Correct |
3 ms |
640 KB |
ok, correct split |
73 |
Correct |
3 ms |
512 KB |
ok, correct split |
74 |
Correct |
4 ms |
640 KB |
ok, correct split |
75 |
Correct |
4 ms |
640 KB |
ok, correct split |
76 |
Correct |
4 ms |
640 KB |
ok, correct split |
77 |
Correct |
4 ms |
640 KB |
ok, correct split |
78 |
Correct |
2 ms |
512 KB |
ok, correct split |
79 |
Correct |
2 ms |
512 KB |
ok, correct split |
80 |
Correct |
3 ms |
640 KB |
ok, correct split |
81 |
Correct |
4 ms |
640 KB |
ok, correct split |
82 |
Correct |
4 ms |
640 KB |
ok, correct split |
83 |
Correct |
4 ms |
640 KB |
ok, correct split |
84 |
Correct |
3 ms |
640 KB |
ok, no valid answer |
85 |
Correct |
3 ms |
512 KB |
ok, correct split |
86 |
Correct |
3 ms |
640 KB |
ok, correct split |
87 |
Correct |
1 ms |
256 KB |
ok, no valid answer |
88 |
Correct |
1 ms |
256 KB |
ok, no valid answer |
89 |
Correct |
3 ms |
512 KB |
ok, no valid answer |
90 |
Correct |
3 ms |
640 KB |
ok, no valid answer |
91 |
Correct |
2 ms |
512 KB |
ok, no valid answer |
92 |
Correct |
3 ms |
640 KB |
ok, no valid answer |
93 |
Correct |
4 ms |
640 KB |
ok, no valid answer |
94 |
Correct |
123 ms |
10536 KB |
ok, correct split |
95 |
Correct |
182 ms |
13688 KB |
ok, correct split |
96 |
Correct |
156 ms |
12536 KB |
ok, correct split |
97 |
Correct |
34 ms |
4216 KB |
ok, correct split |
98 |
Correct |
35 ms |
4088 KB |
ok, correct split |
99 |
Correct |
56 ms |
5880 KB |
ok, correct split |
100 |
Correct |
160 ms |
13432 KB |
ok, correct split |
101 |
Correct |
146 ms |
12148 KB |
ok, correct split |
102 |
Correct |
124 ms |
12016 KB |
ok, correct split |
103 |
Correct |
123 ms |
11504 KB |
ok, correct split |
104 |
Correct |
128 ms |
13668 KB |
ok, correct split |
105 |
Correct |
58 ms |
6308 KB |
ok, correct split |
106 |
Correct |
119 ms |
14056 KB |
ok, correct split |
107 |
Correct |
109 ms |
9848 KB |
ok, correct split |
108 |
Correct |
110 ms |
9832 KB |
ok, correct split |
109 |
Correct |
166 ms |
13304 KB |
ok, correct split |
110 |
Correct |
161 ms |
12856 KB |
ok, correct split |
111 |
Correct |
158 ms |
12784 KB |
ok, correct split |
112 |
Correct |
158 ms |
13296 KB |
ok, correct split |
113 |
Correct |
159 ms |
13296 KB |
ok, correct split |
114 |
Correct |
15 ms |
1792 KB |
ok, correct split |
115 |
Correct |
12 ms |
1664 KB |
ok, correct split |
116 |
Correct |
148 ms |
12528 KB |
ok, correct split |
117 |
Correct |
148 ms |
12272 KB |
ok, correct split |
118 |
Correct |
123 ms |
9852 KB |
ok, correct split |
119 |
Correct |
126 ms |
9720 KB |
ok, correct split |
120 |
Correct |
138 ms |
12152 KB |
ok, correct split |
121 |
Correct |
98 ms |
9464 KB |
ok, no valid answer |
122 |
Correct |
97 ms |
9468 KB |
ok, no valid answer |
123 |
Correct |
139 ms |
12152 KB |
ok, no valid answer |
124 |
Correct |
135 ms |
12152 KB |
ok, no valid answer |
125 |
Correct |
89 ms |
10480 KB |
ok, no valid answer |
126 |
Correct |
57 ms |
9200 KB |
ok, no valid answer |
127 |
Correct |
112 ms |
10988 KB |
ok, no valid answer |