Submission #242736

#	Time	Username	Problem	Language	Result	Execution time	Memory
242736		groeneprof	Split the Attractions (IOI19_split)	C++14	40 / 100	171 ms	34052 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define P(a) do{if(debug)cout<<a<<endl;} while(false);
#define H(a) P(#a<<": "<<a);
using namespace std;
const int inf = 2e9;
const bool debug = 0;

vector<int> ts, mi, size;
vector<bool> open;
vector<int> res;
vector<vector<int> > graph;
int a,b,c,n,va,vb,vc;
int na = 0, nb = 0;
int t = 0;
bool bol = false;
vector<bool> vis;
void dfs2(int u, int& mints);
void dfs3(int u);
int dfs(int u, int p){
	if(open[u]){
		return 0;
	}
	int ms = 0;
	ts[u] = t++;
	mi[u] = ts[u];
	open[u] = true;
	vector<int> realchildren;
	for(int i = 0; i<graph[u].size(); i++) { int v = graph[u][i]; if(v!=p){
		if(!open[v]) realchildren.push_back(i);
		int s = dfs(v,u);
		size[u]+=s;
		ms = max(ms,s);
		mi[u] = min(mi[u], mi[v]);
	} else {
		realchildren.push_back(i);
	}
	}
	if(size[u]>=a&&ms<a&&!bol){
		H(u);
		int p1 = size[u];
		H(p1);
		vector<bool> startA(graph[u].size(),1);
		for(int i : realchildren) {
			int v = graph[u][i];
			if(mi[v]<ts[u] && (p1-size[v]>=a||ts[v]<ts[u])){
				H(v);
				p1-=size[v];
				startA[i] = false;
			}
		}
		if(n-p1>=a){
			if(p1>n-p1){
				swap(va,vb);
				swap(a,b);
			}
			//YES
			//A: dfs starting from children with startA[v] == true, over nodes with ts>ts[u]
			//B: then dfs starting from p, ignoring nodes that already have been chosen
			//C: default option
			res[u] = va;
			vis[u] = true;
			na = 1;
			for(int i : realchildren) if(startA[i]){
				dfs2(graph[u][i],ts[u]);
			}
			dfs3(0);
		}
		else{
			//NO
			//res = {0,0,0,...}
			res.assign(n,0);
		}
		bol = true;
	}
	return size[u];
}


void dfs2(int u, int& mints){
	if(vis[u]||ts[u]<=mints||na>=a){
		return;
	}
	res[u] = va;
	na++;
	vis[u] = true;
	for(int v : graph[u]) {
		dfs2(v,mints);
	}
}

void dfs3(int u){
	if(vis[u]||nb>=b){
		return;
	}
	res[u] = vb;
	nb++;
	vis[u] = true;
	for(int v : graph[u]){
		dfs3(v);
	}
}

vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
	pair<int,int> d[3] = {{A,1},{B,2},{C,3}};
	n = N;
	sort(d, d+3);
	a = d[0].first; b = d[1].first; c = d[2].first;
	va = d[0].second; vb = d[1].second; vc = d[2].second;


	graph.resize(n);
	ts.resize(n,-1);
	mi.resize(n,inf);
	size.resize(n,1);
	vis.resize(n,false);
	open.resize(n, false);
	res.resize(n,vc);

	for(int i = 0; i<p.size();i++){
		graph[p[i]].push_back(q[i]);
		graph[q[i]].push_back(p[i]);
	}
	dfs(0,0);
	return res;	
}

Compilation message (stderr)

split.cpp: In function 'int dfs(int, int)':
split.cpp:29:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<graph[u].size(); i++) { int v = graph[u][i]; if(v!=p){
                 ~^~~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:120:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i<p.size();i++){
                 ~^~~~~~~~~

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