Submission #490647

#	Time	Username	Problem	Language	Result	Execution time	Memory
490647		mraron	Split the Attractions (IOI19_split)	C++14	40 / 100	108 ms	16220 KiB

split

#include "split.h"
#include <array>
#include <iostream>
#include <cassert>
#include <algorithm>
using namespace std;

int n;
vector<int> lvl;
vector<vector<int>> adj;
vector<int> sz;
vector<int> low;
vector<int> par;

void dfs0(int x) {
	sz[x]=1;
	low[x]=lvl[x];
	for(auto i:adj[x]) {
		if(!sz[i]) {
			lvl[i]=lvl[x]+1;
			par[i]=x;
			dfs0(i);
			sz[x]+=sz[i];
			low[x]=min(low[x], low[i]);
		}else if(par[x]!=i) {
			low[x]=min(low[x], lvl[i]);
		}
	}
}

vector<int> st;
vector<int> pars;
int best=0;

void fill_subtree(int x, int c, int& rem, vector<int>& res) {
	if(!rem || res[x]) return ;
	//~ cerr<<x<<" "<<c<<"fill\n";
	rem--;
	res[x]=c;
	
	for(auto i:adj[x]) {
		if(par[x]!=i && lvl[i]==lvl[x]+1 && !res[i]) {
			fill_subtree(i, c, rem, res);
		}
	}
}

bool dfs1(int x, int a, int b, int id1, int id2, vector<int>& res) {
	st[x]=1;
	
	if(par[x]!=-1) {	
		pars.push_back(par[x]);
	
		while(best>=0 && (best>=(int)pars.size() || sz[pars[best]]-sz[x]<a)) best--;
		while(best+1<(int)pars.size() && sz[pars[best+1]]-sz[x]>=a) best++;
		
		if(best>=0 && best<(int)par.size() && sz[pars[best]]-sz[x]>=a) {
			if(sz[x]>=b) { 
				fill_subtree(x, id2, b, res);
				fill_subtree(pars[best], id1, a, res);
				return true;
			}else if(low[x]<best && n-sz[pars[best]]+sz[x]>=b) {
				fill_subtree(x, id2, b, res);
				fill_subtree(pars[best], id1, a, res);
				fill_subtree(pars[low[x]], id2, b, res);
				return true;
			}
		}
		
	}
	
	for(int i:adj[x]) {
		if(!st[i]) {
			if(dfs1(i, a, b, id1, id2, res)) return true;
		}else if(par[x]!=i) {}
	}
	
	if(par[x]!=-1) {
		pars.pop_back();
	}
	
	return false;
}

bool find_sol(int a, int b, int id1, int id2, vector<int>& res) {
	pars.clear();	
	st.assign(n, 0);
	best=0;

	return dfs1(0, a, b, id1, id2, res);
}

vector<int> find_split(int n_, int a, int b, int c, vector<int> p, vector<int> q) {
	n=n_;
	
	adj.assign(n, vector<int>());
	for(int i=0;i<(int)p.size();++i) {
		adj[p[i]].push_back(q[i]);
		adj[q[i]].push_back(p[i]);
	}
	
	sz.assign(n, 0);
	lvl.assign(n, 0);
	low.assign(n, n);
	par.assign(n, -1);
	
	dfs0(0);
	
	vector<int> res(n, 0);
	array<int, 3> x={a,b,c};
	for(int i=0;i<3;++i) {
		for(int j=0;j<3;++j) {
			if(i!=j && find_sol(x[i], x[j], i+1, j+1, res)) {
				
				for(auto& k:res) {
					if(!k) {
						k=1+2+3-(i+1)-(j+1);
						//~ assert(k==0 || k==1 || k==2 || k==3);
						//~ assert(k!=(i+1) && k!=(j+1));
					}
					
				}
				
				assert(count(res.begin(), res.end(), 1)==a);
				assert(count(res.begin(), res.end(), 2)==b);
				assert(count(res.begin(), res.end(), 3)==c);
				
				return res;
			}
		}
	}
	
	return res;
}

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