Submission #526180

#	Time	Username	Problem	Language	Result	Execution time	Memory
526180		lkh3happy	Split the Attractions (IOI19_split)	C++14	100 / 100	136 ms	14908 KiB

split

#include "split.h"
#include <bits/stdc++.h>
using namespace std;

int pa[100001], sz[100001], siz[100001], vis[100001], cnt[4];
vector<int> v[100001], ans;
vector<pair<int, int> > v1;

int find(int x){
    if(pa[x]==-1) return x;
    return pa[x]=find(pa[x]);
}

int uni(int x, int y){
    x=find(x); y=find(y);
    if(x==y) return 0;
    sz[x]+=sz[y]; pa[y]=x;
    return sz[x];
}

int getsz(int prev, int now){
    int s=1;
    for(auto &i:v[now]) if(prev!=i) s+=getsz(now, i);
    return siz[now]=s;
}

int getct(int prev, int now, int n){
    for(auto &i:v[now]) if(prev!=i && siz[i]>n/2) return getct(now, i, n);
    return now;
}

void dfs(int now, int ct, int s, int mx){
    vis[now]=1;
    if(cnt[s]==mx) return;
    cnt[s]++; ans[now]=s;
    for(auto &i:v[now]) if(!vis[i] && ct!=i) dfs(i, ct, s, mx);
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    int x=1, y=2, z=3, m=p.size();
    if(a>b) swap(a, b), swap(x, y);
    if(b>c) swap(b, c), swap(y, z);
    if(a>c) swap(a, c), swap(z, x);
	ans.resize(n);
	for(int i=0;i<=100000;i++) pa[i]=-1, sz[i]=1;
	for(int i=0;i<m;i++){
	    if(uni(p[i], q[i])) v[p[i]].push_back(q[i]), v[q[i]].push_back(p[i]);
	    else v1.push_back({p[i], q[i]});
	}
	getsz(-1, 0);
	int ct=getct(-1, 0, n), po=0, pn;
	for(auto &i:v[ct]) if(getsz(ct, i)>=a) po=1, pn=i;
	if(po){
	    dfs(pn, ct, x, a); dfs(ct, ct, y, b);
	    for(auto &i:ans) if(!i) i=z;
	    return ans;
	}
	for(int i=0;i<=100000;i++) pa[i]=-1, sz[i]=1;
	for(int i=0;i<n;i++) if(i!=ct) for(auto &j:v[i]) if(j!=ct) uni(i, j); 
	for(auto &[i,j]:v1){
	    if(i==ct || j==ct) continue;
	    int s=uni(i, j);
	    if(s) v[i].push_back(j), v[j].push_back(i);
	    if(s>=a){
	        po=1; pn=i; break;
	    }
	}
	if(!po) return ans;
	dfs(pn, ct, x, a); dfs(ct, ct, y, b);
	for(auto &i:ans) if(!i) i=z;
	return ans;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:60:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |  for(auto &[i,j]:v1){
      |            ^

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 24 / 24
• Subtask 5: 36 / 36