Submission #243645

#	Time	Username	Problem	Language	Result	Execution time	Memory
243645		groeneprof	Split the Attractions (IOI19_split)	C++14	18 / 100	160 ms	28920 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<vector<int> > graph;
vector<bool> vis1,vis2;
vector<int> ts,mi,res,size;
int t = 0;
int va,vb,vc;
int a,b,c;
int na = 0, nb = 0, nc = 0;
int n;
bool bol = false;


void dfs2(int u, int& mints);
void dfs3(int u);

int dfs(int u){
	if(vis1[u]) return 0;
	if(ts[u]!=-1) return inf;

	ts[u] = t++;
	mi[u] = ts[u];
	vis1[u] = true;
	vector<int> cs;
	int ma = 0;
	for(int v : graph[u]) {
		int s = dfs(v);
		if(s!=inf){
			size[u]+=s;
			ma = max(ma,s);
		}
		mi[u] = min(mi[u],mi[v]);
		cs.push_back(s);
	}

	if(size[u]>=a && ma<a && !bol){
		H(u);
		H(size[u]);
		H(ma);
		P("a");
		bol = true;
		int p1 = size[u];
		vector<int> startA;
		for(int i = 0; i<graph[u].size(); i++){
			H(cs[i]);
			H(graph[u][i]);
			H(mi[graph[u][i]]);
			if(p1-cs[i]>=a&&mi[graph[u][i]]<ts[u]){
				p1-=cs[i];
			}
			else if(ts[graph[u][i]] > ts[u]){
				startA.push_back(graph[u][i]);
			}
		}
		P(p1);
		if(n-p1>=a){
			if(p1>n-p1){
				swap(a,b);
				swap(va,vb);
			}
			na = 1;
			vis2[u] = true;
			res[u] = va;
			for(int v : startA){
				dfs2(v, ts[u]);
			}
			dfs3(0);
		}
		else{
			res.assign(n,0);
		}
	}
	vis1[u] = false;
	return size[u];
}

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

void dfs3(int u){
	if(vis2[u] || nb>=b){
		return;
	}
	vis2[u] = true;
	res[u] = vb;
	nb++;
	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> aa[3] = {{A,1}, {B,2}, {C,3}};
	sort(aa, aa+3);
	va = aa[0].second; vb = aa[1].second; vc = aa[2].second;
	a = aa[0].first; b = aa[1].first; c = aa[2].first;
	n = N;

	graph.resize(n);
	vis1.resize(n,0);
	vis2.resize(n,0);
	ts.resize(n,-1);
	mi.resize(n,inf);
	res.resize(n,vc);
	size.resize(n,1);

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

Compilation message (stderr)

split.cpp: In function 'int dfs(int)':
split.cpp:50:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i<graph[u].size(); i++){
                  ~^~~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:121: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: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36