Submission #891464

#	Time	Username	Problem	Language	Result	Execution time	Memory
891464		Jawad_Akbar_JJ	Split the Attractions (IOI19_split)	C++17	40 / 100	138 ms	22224 KiB

split

#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <iostream>
#include <vector>
#include <cstdio>
#include <cassert>
#include <algorithm>
#include "split.h"

using namespace std;

const int N = 100005 + 1;
vector<int> nei[N],ch[N];
int color[N],A,B;
vector<vector<int>> v;
int sz[N],blocked = -1;
bool seen[N],found = false;
int root;


void color_it(int u,int c){
	color[u] = c;
	A--;
	if (A == 0)
		return;
	for (int i : ch[u]){
		if (blocked == i)
			continue;
		color_it(i,c);
		if (A==0)
			return;
	}
}



void dfs(int u){
	seen[u] = true;
	sz[u] = 1;
	for (int i : nei[u]){
		if (seen[i])
			continue;
		ch[u].push_back(i);
		dfs(i);
		sz[u] += sz[i];
	}
}

void dfs2(int u){
	for (int i : ch[u]){
		if (found)
			return;
		if (sz[i]>=A and (sz[root] - sz[i]) >= B){
			color_it(i,v[0][1]);
			A = B;
			blocked = i;
			color_it(root,v[1][1]);
			found = true;
			return;
		}
		dfs2(i);
	}
}


vector<int> find_split(int n,int a,int b,int c,vector<int> p,vector<int> q){
	int m = p.size();
	srand(10000);

	for (int i=0;i<m;i++){
		p[i]++;
		q[i]++;
		nei[p[i]].push_back(q[i]);
		nei[q[i]].push_back(p[i]);
	}

	v = {{a,1},{b,2},{c,3}};
	sort(begin(v),end(v));
	A = v[0][0];
	B = v[1][0];
	for (int i=1;i<=20;i++){

		for (int i=1;i<=n;i++)
			ch[i].clear(),seen[i] = false;
		blocked = -1;
		root = rand()%(n+1);
		dfs(root);

		
		dfs2(root);
		if (!found)
			continue;
		vector<int> ans;

		for (int i=1;i<=n;i++){
			if (found and color[i]==0)
				ans.push_back(v[2][1]);
			else
				ans.push_back(color[i]);
		}
		return ans;
	}

	vector<int> ans;

	for (int i=1;i<=n;i++)
		ans.push_back(0);
	
	return ans;
}

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