| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1285865 | trandangquang | Split the Attractions (IOI19_split) | C++20 | 0 ms | 0 KiB |
#include"split.h"
#include<bits/stdc++.h>
using namespace std;
#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ll long long
#define _ << " " <<
template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}
const int MAXN=101010;
int n;
vector<int> adj[MAXN];
ii a[3];
void init(int N, int A, int B, int C, vector<int> &p, vector<int> &q){
n=N;
rep(i,sz(p)){
adj[p[i]].eb(q[i]);
adj[q[i]].eb(p[i]);
}
/// a<=b && b<=c
a[0]={A,1}; a[1]={B,2}; a[2]={C,3};
sort(a,a+3);
/// wait have to change something here
}
/**
thuat toan: bay gio xet moi dinh thap nhat ma co gtri >= a
-> xet phan con lai coi >= a hay khong
neu co, lay gia tri nho hon lm a, gtri lon hon lm b
neu khong, lay cac goc trong cay con xong push cho ngoai sao cho o trong vx con >= a dinh
cuoi cung, lay nhung dinh c co deg = 1 va cu the ...
**/
int tin[MAXN],tout[MAXN],low[MAXN],par[MAXN],sz[MAXN],tour[MAXN],tim;
vector<int> tree[MAXN];
bool isOpt[MAXN];
void dfs(int u, int p=-1){
par[u]=p; sz[u]=1;
tin[u]=low[u]=++tim;
tour[tim]=u;
int mxc=0;
for(int v:adj[u]) if(v!=p){
if(!tin[v]){
dfs(v,u);
tree[u].eb(v);
sz[u]+=sz[v];
maxi(mxc,sz[v]);
low[u]=min(low[u],low[v]);
} else{
low[u]=min(low[u],tin[v]);
}
}
tout[u]=tim;
if(sz[u]>=a[0].fi && mxc<a[0].fi) isOpt[u]=1;//,cout<<u<<'\n';
}
void buildTree(){
dfs(0);
}
bool used[MAXN];
vector<int> setA,setB;
bool isSatisfied(){
rep(u,n) if(isOpt[u]){
int out=n-sz[u], in=sz[u];
vector<int> trans;
for(int v:tree[u]){
if(low[v]<tin[u] && in-sz[v]>=a[0].fi){
in-=sz[v];
out+=sz[v];
trans.eb(v);
}
}
if(in>=a[0].fi && out>=a[0].fi){
foru(i,1,tin[u]-1) setB.eb(tour[i]);
foru(i,tout[u]+1,n) setB.eb(tour[i]);
for(int v:trans){
foru(i,tin[v],tout[v]) setB.eb(tour[i]),used[i]=1;
}
foru(i,tin[u],tout[u]) if(!used[i]) setA.eb(tour[i]);
return true;
}
}
return false;
}
int mark[MAXN]; bool omit[MAXN];
int deg[MAXN],parD[MAXN]; bool isIn[MAXN];
int find(int x){
return parD[x]==x?x:parD[x]=find(parD[x]);
}
bool unite(int x, int y){
x=find(x); y=find(y);
if(x!=y){
parD[y]=x;
return true;
}
return false;
}
void hehe(vector<int> arr, int num, int id){
// cerr<<num _ id<<'\n';
memset(isIn,0,sizeof(isIn));
memset(deg,0,sizeof(deg));
iota(parD,parD+n,0);
for(int i:arr) isIn[i]=1;
for(int i:arr){
for(int j:adj[i]) if(isIn[j]){
if(unite(i,j)){
++deg[i]; ++deg[j];
}
}
}
vector<int> vt;
for(int i:arr) if(deg[i]==1) vt.eb(i);
foru(i,1,sz(arr)-num){
int u=vt.back();vt.pop_back();
omit[u]=true;
for(int v:adj[u]) if(isIn[v]){
deg[v]--;
if(deg[v]==1) vt.eb(v);
}
}
for(int i:arr) if(!omit[i]) mark[i]=id;
}
vector<int> hihi(){
vector<int> res(n);
rep(i,n) res[i]=mark[i];
return res;
}
vector<int> answer(){
if(!isSatisfied()){
return hihi();
}
if(sz(setA)>sz(setB)) swap(setA,setB);
hehe(setA,a[0].fi,a[0].se);
hehe(setB,a[1].fi,a[1].se);
rep(i,n) if(mark[i]==0) mark[i]=a[2].se;
return hihi();
}
vector<int> find_split(int N, int A, int B, int C, vector<int> &p, vector<int> &q){
init(N,A,B,C,p,q);
buildTree();
// cout<<isSatisfied();
return answer();
}