Submission #143975

#	Time	Username	Problem	Language	Result	Execution time	Memory
143975		sasa	Split the Attractions (IOI19_split)	C++14	40 / 100	288 ms	39112 KiB

split

#include "split.h"
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <deque>
#include <assert.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <stdio.h>
#include <string.h>
#include <utility>
#include <math.h>
#include <bitset>
#include <iomanip>
#include <complex>
using namespace std;
//#define int long long
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long double ld;
typedef long long ll;
#define X first
#define Y second
#define all(o) o.begin(), o.end()
#define endl '\n'
using namespace std;
const int maxn = 2e5 + 10;
vi adj[maxn], tree[maxn], oth[maxn];
vi g[maxn];
 
int num[3], ans[maxn], sz[maxn], comp[maxn];
bool mark[maxn];
void dfs(int v){
	mark[v] = 1;
	for(auto u : adj[v]){
		if(!mark[u]){
			tree[v].push_back(u);
			tree[u].push_back(v);
			dfs(u);
		}
		else{
			oth[u].push_back(v);
			oth[v].push_back(u);
		}
	}
}
bool markTree[maxn];
void dfs_tree(int v,int root){
	sz[v] = 1;
	if(v == root){
		memset(markTree, 0, sizeof markTree);
		comp[v] = -1;
	}
	if(markTree[v])
		return;
	markTree[v] = 1;
	for(auto u : tree[v]){
		if(markTree[u])
			continue;
		if(v == root)
			comp[u] = u;
		else
			comp[u] = comp[v];
		dfs_tree(u, root);
		sz[v] += sz[u];
	}
}
int Rem;
void dfs_g(int v){
	if(mark[v])
		return;
	mark[v] = 1;
	Rem -= sz[v];
	if(Rem <= 0) return;
	for(auto u : g[v])
		dfs_g(u);
 
}
int answer[maxn];
int rems = 0;
void dfs_ok(int v,int col){
	if(mark[v] || ans[v] != col || rems <= 0)
		return;
	rems--;
	answer[v] = col;
	mark[v] = 1;
	for(auto u : adj[v])
		dfs_ok(u, col);
}
void make_ok(int n){
	for(int i=0; i<n; i++)
		answer[i] = 3;
	rems = num[0];
	memset(mark, 0, sizeof mark);
	for(int i=0; i<n; i++)
		if(ans[i] == 1){
			dfs_ok(i, 1);
			break;
		}
	rems = num[1];
	memset(mark, 0, sizeof mark);
	for(int i=0; i<n; i++)
		if(ans[i] == 2){
			dfs_ok(i, 2);
			break;
		}
}
vector<int> find_split(int n, int a1, int b1, int c1, vector<int> from, vector<int> to) {
	int m = from.size();
	num[0] = a1, num[1] = b1, num[2] = c1;
	sort(num, num + 3);
	
	for(int i=0; i<m; i++){
		int u = from[i], v = to[i];
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(0);
	dfs_tree(0, 0);
	int root = 0;
	while(1){
		int bef = root;
		for(auto u : tree[root]){
			if(sz[u] > n/2 && sz[u] < sz[root])
				root = u;
		}
		if(bef == root)
			break;
	}
	memset(sz, 0, sizeof sz);
	dfs_tree(root, root);
	bool can = true;
	if(m == n - 1){
		can = false;
		for(auto u : tree[root]){
			if(sz[u] >= num[0]){
				for(int i=0; i<n; i++)
					ans[i] = (comp[i] == u ? 1 : 2);
				can = true;
				break;
			}
		}
		make_ok(n);
	}
	else{
		for(int i=0; i<n; i++){
			for(auto j : oth[i]){
				if(j != root && i != root){
					int u = comp[i];
					int v = comp[j];
					if(u != v){
						g[u].push_back(v);
						g[v].push_back(u);
					}
				}
			}
		}
		can = false;
		for(auto u : tree[root]){
			if(sz[u] >= num[0]){
				for(int i=0; i<n; i++)
					ans[i] = (comp[i] == u ? 1 : 2);
				can = true;
				break;
			}
		}
		if(!can){
			Rem = num[0];
			memset(mark, 0, sizeof mark);
			for(auto u : tree[root])
				dfs_g(u);
			for(int i=0; i<n; i++){
				if(i != root && mark[comp[i]])
					ans[i] = 1;
				else
					ans[i] = 2;
			}
			can = true;
		}
		make_ok(n);
	}/*
	cout << "CAN" << can << endl;
	for(int i=0; i<n; i++)
		cout << answer[i] << " ";
	cout << endl;*/
	pii per[3];
	per[0] = {a1, 1};
	per[1] = {b1, 2};
	per[2] = {c1, 3};
	sort(per, per + 3);
	vi res;
	res.resize(n);
	if(can){
		for(int i=0; i<n; i++)
			res[i] = per[answer[i] - 1].Y;
	}
	return res;
}
/*
int main(){
	int n, m;
	cin >> n >> m;
	int a1, b1, c1;
	cin >> a1 >> b1 >> c1;
	vi fr, to;
	for(int i=0; i<m; i++){
		int x, y;
		cin >> x >> y;
		fr.push_back(x);
		to.push_back(y);
	}
	vi res = find_split(n, a1, b1, c1, fr, to);
	for(auto t : res)
		cout << t << " ";
	cout << endl;
}*/

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