Submission #490636

#	Time	Username	Problem	Language	Result	Execution time	Memory
490636		mraron	Rectangles (IOI19_rect)	C++14	Compilation error	0 ms	0 KiB

rect

#include "split.h"
#include <array>
#include <iostream>
#include <cassert>
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 ;
	rem--;
	assert(c==1 || c==2 || c==3);
	res[x]=c;
	
	for(auto i:adj[x]) {
		if(par[x]!=i && !res[i]) {
			fill_subtree(i, c, rem, res);
		}
	}
}

bool dfs1(int x, int a, int b, int id1, int id2, vector<int>& res) {
	//~ cerr<<x<<" "<<a<<" "<<b<<"\n"<<flush;
	st[x]=1;
	
	if(par[x]!=-1) {	
		pars.push_back(par[x]);
	
		while(best>=0 && (best>=(int)pars.size() || -sz[x]+sz[pars[best]]<a)) best--;
		while(best+1<(int)pars.size() && -sz[x]+sz[pars[best+1]]>=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);
				//~ assert(b==0 && a==0);
				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);
				//~ assert(b==0 && a==0);
				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);
				}
				
				return res;
			}
		}
	}
	
	return res;
}

Compilation message (stderr)

rect.cpp:1:10: fatal error: split.h: No such file or directory
    1 | #include "split.h"
      |          ^~~~~~~~~
compilation terminated.