| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1290835 | enzy | Split the Attractions (IOI19_split) | C++20 | 0 ms | 0 KiB |
#include "split.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
vector<int>v[maxn], filhos[maxn];
int marc[maxn], sub[maxn], pai[maxn], cor[maxn], val[maxn], prof[maxn], ja[maxn];
pair<int,int>z[3];
int calc(int u, int x, int c, int lim){
ja[u]++;
if(x){
cor[u]=c;
x--;
}
for(int viz : v[u]){
if(ja[viz]||prof[viz]<lim) continue;
x=calc(viz,x,c,lim);
}
return x;
}
int termina(int u, int x, int c){
ja[u]++;
if(x){
cor[u]=c;
x--;
}
for(int viz : v[u]){
if(ja[viz]) continue;
x=termina(viz,x,c);
}
return x;
}
void dfs(int u){
marc[u]++;
sub[u]=1;
int ma=0;
for(int viz : v[u]){
if(pai[u]==viz) continue;
if(marc[viz]){
if(prof[viz]<prof[u]){
// marcando as backedges
val[u]++;
val[viz]--;
}
continue;
}
filhos[u].push_back(viz);
pai[viz]=u;
prof[viz]=prof[u]+1;
dfs(viz);
ma=max(ma,sub[viz]);
sub[u]+=sub[viz];
val[u]+=val[viz];
}
if(sub[u]>=a&&ma<a){ // achei o cara com a propriedade
int x=sub[u], y=n-sub[u];
vector<int>aux;
for(int viz : filhos[u]){
if(val[viz]){ // ou seja tem backedge para cima
if(x-sub[viz]>=z[0].first){
aux.push_back(viz);
x-=sub[viz];
}else{ // deu bom já
for(int viz : aux) z[1].first=calc(viz,z[1].first,z[1].second,prof[viz]);
for(int viz : v[u]) if(!ja[viz]) z[0].first=calc(viz,z[0].first,z[0].second,prof[viz]);
if(z[0].first){
cor[u]=z[0].second;
z[0].first--;
}
z[1].first=termina(pai[u],z[1].first,z[1].second);
goto sair;
}
}
}
}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
for(int i=0;i<p.size();i++){
v[p[i]].push_back(q[i]);
v[q[i]].push_back(p[i]);
}
z[0]={a,1}; z[1]={b,2}; z[2]={c,3};
sort(z,z+3);
dfs(1);
sair:;
vector<int>resp(n,0);
for(int i=0;i<n;i++){
if(cor[i]) resp[i]=cor[i];
else resp[i]=z[2].second;
}
return resp;
}