// 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(dsu.data[root]<0 and -dsu.data[root]>=sizes[0].first);
assert(std::is_sorted(begin(sizes), end(sizes)));
std::vector<int> result(n, sizes[2].second);
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);
}
auto const process=[&](std::pair<int, int> const item, int const startNode, auto condition){
auto const [size, componentId]=item;
std::vector<int> queue;
queue.push_back(startNode);
assert(result[startNode]!=componentId); result[startNode]=componentId;
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)){
queue.push_back(other); result[other]=componentId;
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(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 |
Runtime error |
1 ms |
384 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
384 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
ok, correct split |
| 2 |
Correct |
1 ms |
256 KB |
ok, no valid answer |
| 3 |
Runtime error |
2 ms |
384 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
384 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
