Submission #1237632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237632		MuhammadSaram	Split the Attractions (IOI19_split)	C++20	100 / 100	63 ms	15688 KiB

split

#include "split.h"
#include <bits/stdc++.h>

using namespace std;

const int M = 1e5;

vector<int> nei[M], cc;
int subt[M], dep[M], mnd[M];
bool vis[M];

void init(int u)
{
	subt[u]=1, vis[u]=1;
	mnd[u]=dep[u];
	for (int i:nei[u])
		if (!vis[i])
			dep[i]=dep[u]+1, init(i), mnd[u]=min(mnd[u],mnd[i]), subt[u]+=subt[i];
		else
			mnd[u]=min(mnd[u],dep[i]);
}

void dfs(int u, int a)
{
	cc.push_back(u);
	vis[u]=1;
	for (int i:nei[u])
	{
		if (cc.size()==a) break;
	 	if(!vis[i])
			dfs(i,a);
	}	
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q)
{
	int m=p.size();
	for (int i=0;i<m;i++)
		nei[p[i]].push_back(q[i]), nei[q[i]].push_back(p[i]);
	init(0);
	vector<int> ans(n);
	vector<pair<int,int>> ord={{a,1},{b,2},{c,3}};
	sort(ord.begin(),ord.end());
	a=ord[0].first, b=ord[1].first;
	int u;
	for (int i=0;i<n;i++)
	{
		bool b=(subt[i]>=a);
		for (int v:nei[i])
			if (dep[v]==dep[i]+1)
				b&=(subt[v]<a);
		if (b) u=i;
	}
	int x=n-subt[u];
	for (int i=0;i<n;i++)
		if (dep[i]>dep[u]) vis[i]=0;
	for (int i:nei[u])
	{
		if (x>=a) break;
		if (dep[i]==dep[u]+1 && mnd[i]<dep[u])
			x+=subt[i], subt[u]-=subt[i], dfs(i,n+1), cc.clear();
	}
	if (x<a) return ans;
	if (max(subt[u],x)==subt[u])
		swap(a,b),swap(ord[0],ord[1]);
	dfs(u,a);
	for (int i=0;i<n;i++) vis[i]=0;
	for (int i:cc) vis[i]=1,ans[i]=ord[0].second;
	cc.clear();
	dfs(0,b);
	for (int i:cc) ans[i]=ord[1].second;
	for (int i=0;i<n;i++)
		if (!ans[i]) ans[i]=ord[2].second;
	
	return ans;
}

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