Submission #257752

#	Time	Username	Problem	Language	Result	Execution time	Memory
257752		maximath_1	Split the Attractions (IOI19_split)	C++17	100 / 100	171 ms	24276 KiB

split

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

vector<int> ans, disc, low, sz, par;
vector<int> adj[100005], adj_st[100005];
pair<int, int> a[3];
int n, m, A, B, C, timer = 0;

void init(){
	a[0] = {A, 1}; a[1] = {B, 2}; a[2] = {C, 3};
	sort(a, a + 3);
	disc.assign(n, 0); low.assign(n, 0);
	sz.resize(n); par.resize(n, -1);
	ans.assign(n, a[2].second);
}

void dfs(int nw){
	sz[nw] = 1;
	disc[nw] = low[nw] = ++timer;
	for(int nx : adj[nw]){
		if(nx != par[nw]){
			if(!low[nx]){
				par[nx] = nw; dfs(nx);
				sz[nw] += sz[nx];
				low[nw] = min(low[nw], low[nx]);
				adj_st[nw].push_back(nx);
			}else{
				low[nw] = min(low[nw], disc[nx]);
			}
		}
	}
	return;
}

int cnt, col;
void fill_ans(int nw, int tp){
	cnt --; ans[nw] = col;
	if(!tp){
		for(int nx : adj_st[nw])
			if(cnt) fill_ans(nx, tp);
	}else{
		for(int nx : adj[nw])
			if(cnt && ans[nx] == a[2].second) fill_ans(nx, tp);
	}
}

vector<int> find_split(int N, int _A, int _B, int _C, vector<int> P, vector<int> Q){
	n = N; m = P.size();
	A = _A, B = _B, C = _C;
	init();

	for(int i = 0; i < m; i ++){
		adj[P[i]].push_back(Q[i]);
		adj[Q[i]].push_back(P[i]);
	}
	par[0] = -1;
	dfs(0);

	int rt = 0;
	for(;;){
		bool found = true;
		for(int nx : adj_st[rt]){
			if(sz[nx] >= a[0].first){
				found = false;
				rt = nx; break;
			}
		}
		if(found) break;
	}

	if(sz[rt] + a[1].first <= n){
		cnt = a[0].first, col = a[0].second;
		fill_ans(rt, 0);
		
		cnt = a[1].first, col = a[1].second;
		fill_ans(par[rt], 1);
	}else{
		cnt = a[1].first, col = a[1].second;
		ans[rt] = col; cnt --;
		for(int nx : adj_st[rt]) 
			if(cnt && low[nx] < disc[rt]) //prioritize
				fill_ans(nx, 0);
		for(int nx : adj_st[rt])
			if(cnt && low[nx] >= disc[rt])
				fill_ans(nx, 0);

		cnt = a[0].first, col = a[0].second;
		if(par[rt] != -1) fill_ans(par[rt], 1);
		if(cnt) ans = vector<int> (n, 0);
	}

	return ans;
}

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