#include "split.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
using namespace std;
const int N = 1e5+5;
int n, m;
vector<int> edges[N];
vector<int> g[N];
bool used[N];
int subtree_size[N];
vector<pii> extra;
void Dfs(int u, int p=-1){
used[u] = true;
subtree_size[u] = 1;
for(auto v : edges[u]){
if(used[v]){
if(v != p)extra.pb({u,v});
continue;
}
g[u].pb(v);
g[v].pb(u);
Dfs(v,u);
subtree_size[u] += subtree_size[v];
}
}
int find_centroid(int u, int p){
for(auto v : g[u]){
if(v!=p && subtree_size[v] > n/2)return find_centroid(v,u);
}return u;
}
void recalc_size(int u, int p){
subtree_size[u] = 1;
for(auto v : g[u]){
if(v == p)continue;
recalc_size(v,u);
subtree_size[u] += subtree_size[v];
}
}
// start of DSU
vector<int> p, sz;
void Init(int n){
p.assign(n,0);
sz.assign(n,1);
for(int i=0;i<n;i++)p[i]=i;
}
int par(int u){
if(p[u] == u)return u;
return p[u] = par(p[u]);
}
bool IsSame(int u, int v){
return par(u) == par(v);
}
void merge(int u,int v){
u=par(u);v=par(v);
if(u == v)return;
p[v] = u;
sz[u] += sz[v];
return;
}
int size_of_node(int u){
return sz[par(u)];
}// end of DSU
pii sizes[3];
vector<int> ans;
int center;
int remaining;
void color(int u){
used[u] = true;
ans[u] = sizes[0].second;
remaining--;
if(not remaining)return;
for(auto v : g[u]){
if(not remaining)return;
if(used[v] || v == center)continue;
color(v);
}
}
void colorB(int u){
used[u] = true;
ans[u] = sizes[1].second;
remaining--;
if(not remaining)return;
for(auto v : edges[u]){
if(not remaining)return;
if(used[v])continue;
colorB(v);
}
}
vector<int> find_split(int N, int a, int b, int c, vector<int> P, vector<int> Q) {
Init(N);
sizes[0] = {a,1};
sizes[1] = {b,2};
sizes[2] = {c,3};
sort(sizes,sizes+3);
a = sizes[0].first;
b = sizes[1].first;
c = sizes[2].first;
n=N; m = P.size();
for(int i=0;i<m;i++){
edges[P[i]].pb(Q[i]);
edges[Q[i]].pb(P[i]);
}
ans.assign(n,sizes[2].second);
Dfs(0);
center = find_centroid(0,0);
recalc_size(center,center);
for(int u=1;u<n;u++){
for(auto v : g[u]){
//~ cout << u << '-' << v << '\n';
if(v != 0)merge(u,v);
}
}
for(auto [u, v] : extra){
if(IsSame(u,v))continue;
g[u].pb(v);
g[v].pb(u);
merge(u,v);
if(size_of_node(u) > a){
// yay we found solution! (I hope)
remaining = a;
memset(used,0,sizeof used);
color(u);
colorB(center);
return ans;
}
}
return vector<int>(n,0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4972 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4972 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4972 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5100 KB |
invalid split: #1=0, #2=2, #3=7 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4972 KB |
jury found a solution, contestant did not |
| 2 |
Halted |
0 ms |
0 KB |
- |
