제출 #1198310

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198310		Muhammet	Split the Attractions (IOI19_split)	C++20	18 / 100	69 ms	48456 KiB

split

#include "bits/stdc++.h"
#include "split.h"
// #include "grader.cpp"

using namespace std;

#define ll long long
#define SZ(s) s.size()
#define ff first
#define ss second

const int N = 2e5 + 5;

int n, ind = -1, cnt;

vector <int> v[N], u[N], vis, p, d, deg, vn, res;

vector <pair <int, int>> v1; 

int bld(int x, int y) {
	p[x] = y;
	d[x] = vis[x] = true;
	for(auto i : v[x]) {
		if(!vis[i]) {
			u[x].push_back(i);
			d[x] += bld(i, x);
		}
	}
	return d[x];
}

void dfs(int x) {
	bool tr = 0;
	for(auto i : u[x]) {
		if(i == p[x]) continue;
		if(d[i] >= v1[0].ff) {
			dfs(i);
			tr = 1;
		}
	}
	if(tr) return;
	queue <int> q, b;
	q.push(x);
	while(!q.empty()) {
		int y = q.front();
		q.pop();
		bool tr1 = 0;
		for(auto i : v[y]) {
			if(p[i] != x and i != p[y] and !tr1) {
				b.push(y);
				tr1 = true;
			}
		} 
		for(auto i : u[y]) {
			q.push(i);
		}
	}
	int k = (n - d[x]);
	while(!b.empty() and k < v1[1].ff) {
		int y = b.front();
		b.pop();
		vn[y] = true;
		deg[p[y]]++;
		if(deg[p[y]] == SZ(u[p[y]])) b.push(p[y]);
		k++;
	}
	if(k >= v1[1].ff) ind = x;
}

void f() {
	for(int i = 0; i < n; i++) {
		u[i].clear();
	}
	vis.assign(n, 0), p.assign(n, 0), d.assign(n, 0), deg.assign(n, 0), vn.assign(n, 0);
	bld(0, -1);
	dfs(0);
}

void df(int x) {
	if(!cnt) return;
	res[x] = v1[0].ss;
	if(!(--cnt)) return;
	for(auto i : u[x]) {
		if(!vn[i]) df(i);
	}
}

void df1(int x) {
	if(!cnt) return;
	res[x] = v1[1].ss;
	if(!(--cnt)) return;
	for(auto i : v[x]) {
		if(!res[i]) df1(i);
	}
}

vector <int> f1() {
	cnt = v1[0].ff;
	df(ind);
	cnt = v1[1].ff;
	df1(p[ind]);
	for(int i = 0; i < n; i++) {
		if(!res[i]) res[i] = v1[2].ss;
	}
	return res;
}

vector<int> find_split(int NN, int a, int b, int c, vector<int> u1, vector<int> u2) {
	n = NN;
	int m = SZ(u1);
	for(int i = 0; i < m; i++) {
		v[u1[i]].push_back(u2[i]);
		v[u2[i]].push_back(u1[i]);
	}
	v1.push_back({a, 1});
	v1.push_back({b, 2});
	v1.push_back({c, 3});
	sort(v1.begin(), v1.end());
	res.assign(n, 0);
	f();
	if(~ind) return f1();
	swap(v1[0], v1[1]);
	f();
	if(~ind) return f1();
	return res;
}

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