Submission #893540

#	Time	Username	Problem	Language	Result	Execution time	Memory
893540		MuhammadSaram	Split the Attractions (IOI19_split)	C++17	100 / 100	89 ms	23932 KiB

split

#include <bits/stdc++.h>

using namespace std;

const int M = 1e5;

vector<int> nei[M],v, chi[M], ans;
bool vis[M];
int col[3],subt[M],dep[M],mndep[M],cnt;

void dfs(int u)
{
	vis[u]=true;
	subt[u]=1;
	mndep[u]=dep[u];
	for (int i:nei[u])
		if (!vis[i])
		{
			dep[i]=dep[u]+1;
			dfs(i);
			mndep[u]=min(mndep[u],mndep[i]);
			subt[u]+=subt[i];
			chi[u].push_back(i);
		}
		else
			mndep[u]=min(mndep[u],dep[i]);
}

void dfs1(int u)
{
	if (!cnt)
		return;
	vis[u]=true;
	ans[u]=col[1];
	cnt--;
	for (int i:nei[u])
		if (!vis[i])
			dfs1(i);
}

vector<int> find_split(int n,int a,int b,int c,vector<int> p,vector<int> q)
{
	for (int i=0;i<n;i++)
		ans.push_back(0);
	v={a,b,c};
	sort(v.begin(),v.end());
	for (int i=0;i<3;i++)
	{
		if (v[i]==a)
		{
			col[i]=1;
			a=-1;
		}
		else if(v[i]==b)
		{
			col[i]=2;
			b=-1;
		}
		else
		{
			col[i]=3;
			c=-1;
		}
	}
	a=v[0],b=v[1],c=v[2];
	for (int i=0;i<p.size();i++)
	{
		nei[p[i]].push_back(q[i]);
		nei[q[i]].push_back(p[i]);
	}
	dfs(0);
	int u=0;
	while (1)
	{
		bool x=false;
		for (int i:chi[u])
			if (subt[i]>=a)
			{
				u=i;
				x=true;
				break;
			}
		if (x)
			continue;
		for (int i=0;i<n;i++)
			vis[i]=(i==u);
		int fsize=1;
		for (int i:chi[u])
			if (mndep[i]>=dep[u])
			{
				fsize+=subt[i];
				vis[i]=true;
			}
		for (int i=0;i<chi[u].size() and fsize<a;i++)
			if (mndep[chi[u][i]]<dep[u])
			{
				fsize+=subt[chi[u][i]];
				vis[chi[u][i]]=true;
			}
		if (fsize>=b and n-fsize>=a)
			swap(a,b),swap(col[0],col[1]);
		else if(n-fsize<b)
			break;
		queue<int> q;
		ans[u]=col[0];
		for (int i:chi[u])
			if (vis[i])
				q.push(i);
		while (!q.empty() and cnt<a-1)
		{
			int x=q.front();
			q.pop();
			vis[x]=true;
			cnt++;
			ans[x]=col[0];
			for (int i:chi[x])
				q.push(i);
		}
		cnt=b;
		dfs1(0);
		for (int i=0;i<n;i++)
			if (!ans[i])
				ans[i]=col[2];
		break;
	}
	return ans;
}

Compilation message (stderr)

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  for (int i=0;i<p.size();i++)
      |               ~^~~~~~~~~
split.cpp:94:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for (int i=0;i<chi[u].size() and fsize<a;i++)
      |                ~^~~~~~~~~~~~~~

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