Submission #954739

#	Time	Username	Problem	Language	Result	Execution time	Memory
954739		waldi	Split the Attractions (IOI19_split)	C++17	22 / 100	162 ms	41592 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int((x).size()))
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;

struct fnu{
	vector<int> r;
	fnu(int n){
		r.resize(n);
		REP(i, n) r[i] = i;
	}
	int f(int x){
		if(r[x] != x) r[x] = f(r[x]);
		return r[x];
	}
	void u(int a, int b){
		a = f(a), b = f(b), r[a] = b;
	}
};

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q){
	vector<int> kolor = {1, 2, 3};
	if(b > c) swap(b, c), swap(kolor[1], kolor[2]);
	if(a > b) swap(a, b), swap(kolor[0], kolor[1]);
	if(b > c) swap(b, c), swap(kolor[1], kolor[2]);
	
	int m = ssize(p);
	vector<vector<pii>> g(n);
	REP(i, m){
		int a = p[i], b = q[i];
		g[a].emplace_back(b, i);
		g[b].emplace_back(a, i);
	}
	
	fnu janusz(m);
	vector<int> odw(n, 0), gl(n, 0), low(n, -1);
	function<void(int, int)> dfs = [&](int w, int id_o){
		odw[w] = 1;
		low[w] = gl[w];
		for(pii i : g[w]) if(i.se != id_o){
			if(!odw[i.fi]){
				gl[i.fi] = gl[w]+1;
				dfs(i.fi, i.se);
				if(low[i.fi] < gl[w]) janusz.u(id_o, i.se);
				low[w] = min(low[w], low[i.fi]);
			}
			else if(gl[i.fi] < gl[w]){
				janusz.u(id_o, i.se);
				low[w] = min(low[w], gl[i.fi]);
			}
		}
	};
	dfs(0, -1);
	
	int it = 0;
	vector<int> skal(m, -1);
	vector<int> spojna(m);
	REP(i, m){
		int t = janusz.f(i);
		if(skal[t] < 0) skal[t] = it++;
		spojna[i] = skal[t];
	}
	
	//~ REP(i, m) printf("%d: %d\n", i, spojna[i]);
	
	vector<vector<int>> sklad(it);
	
	vector<vector<int>> drz(it);
	vector<int> waga(it, 0);
	
	REP(w, n){
		set<int> sas;
		for(pii i : g[w]) sas.emplace(spojna[i.se]);
		if(ssize(sas) == 1){
			sklad[*sas.begin()].emplace_back(w);
			++waga[*sas.begin()];
			continue;
		}
		sklad.push_back({w});
		waga.emplace_back(1);
		drz.emplace_back();
		for(int x : sas){
			drz[it].emplace_back(x);
			drz[x].emplace_back(it);
		}
		++it;
	}
	
	//~ printf("it: %d\n", it);
	//~ REP(i, it){
		//~ printf("%d: ", i);
		//~ for(int x : sklad[i]) printf("%d ", x);
		//~ printf("\n");
	//~ }
	
	//~ printf("drz:\n");
	//~ REP(i, it){
		//~ printf("%d: ", i);
		//~ for(int x : drz[i]) printf("%d ", x);
		//~ printf("\n");
	//~ }
	
	vector pdd = waga;
	vector<int> oj(it);
	function<void(int, int)> dfs_pdd = [&](int w, int o){
		oj[w] = o;
		for(int i : drz[w]) if(i != o) dfs_pdd(i, w), pdd[w] += pdd[i];
	};
	dfs_pdd(0, -1);
	
	REP(xd, 2){
		int ktory = -1;
		REP(i, it) if(pdd[i] >= a){
			if(n-pdd[i] >= b){
				ktory = i;
				break;
			}
		}
		if(ktory >= 0){
			vector czy(n, 0);
			function<void(int)> dfs_odzyskaj = [&](int w){
				for(int x : sklad[w]) czy[x] = 1;
				for(int i : drz[w]) if(i != oj[w]) dfs_odzyskaj(i);
			};
			dfs_odzyskaj(ktory);
			
			//~ REP(i, n) if(czy[i]) printf("czy: %d\n", i);
			
			vector ret(n, kolor[2]);
			function<void(int)> dfs_pomaluj_a = [&](int w){
				//~ printf("a: %d\n", w);
				if(!a) return;
				ret[w] = kolor[0], --a;
				for(auto [i, jajco] : g[w]) if(czy[i] && ret[i] == kolor[2]) dfs_pomaluj_a(i);
			};
			function<void(int)> dfs_pomaluj_b = [&](int w){
				//~ printf("b: %d\n", w);
				if(!b) return;
				ret[w] = kolor[1], --b;
				for(auto [i, jajco] : g[w]) if(!czy[i] && ret[i] == kolor[2]) dfs_pomaluj_b(i);
			};
			REP(i, n) if(czy[i]){dfs_pomaluj_a(i); break;}
			REP(i, n) if(!czy[i]){dfs_pomaluj_b(i); break;}
			return ret;
		}
		swap(a, b);
		swap(kolor[0], kolor[1]);
	}
	return vector(n, 0);
}

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