Submission #1031094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031094		Marco_Escandon	Split the Attractions (IOI19_split)	C++17	11 / 100	64 ms	15628 KiB

split

#include <cstdio>
#include <cassert>

using namespace std;

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> G[100005];
vector<int> v,sts,v2;
ll pl=0, temp;
ll dfs(ll node,ll Padre)
{
	if(v2[node]!=0) return 0;
	v2[node]=1;
	sts[node]=1;
	for(auto i:G[node])
	{
		if(i!=Padre)
		sts[node]+=dfs(i,node);
	}
	if(sts[node]>=temp&&pl==0)
	{
		pl=1;
		temp=node;
	}
	return sts[node];
}
void fill(ll node, ll c, ll color)
{
	queue<ll> q;
	v[node]=color;c--;
	q.push(node);
	while(!q.empty())
	{
		for(auto i:G[q.front()])
		{
			if(sts[i]<sts[q.front()]&&c>0&&v[i]==0)
			{
				v[i]=color;
				c--;
				q.push(node);
			}
		}
		q.pop();
	}
}
void fill2(ll node, ll c, ll color)
{
	queue<ll> q;
	v[node]=color;c--;
	q.push(node);
	while(!q.empty())
	{
		for(auto i:G[q.front()])
		{
			if(c>0&&v[i]==0)
			{
				v[i]=color;
				c--;
				q.push(i);
			}
		}
		q.pop();
	}
}
vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	for(int i=0; i<p.size(); i++)
	{
		G[p[i]].push_back(q[i]);
		G[q[i]].push_back(p[i]);
	}
	pair<ll,ll> cad[]={{a,1},{b,2},{c,3}}; sort(cad,cad+3); temp=cad[0].first;
	v.assign(n,0); sts.assign(n,0),v2.assign(n,0);
	dfs(0,-1);
	if(n-sts[temp]<cad[0].first)
	{
		return v;
	}
	if(sts[temp]*2>n)
	{
		swap(cad[0],cad[1]);
	}
	fill(temp,cad[0].first,cad[0].second);
	fill2(0,cad[1].first,cad[1].second);
	for(int i=0; i<n; i++)
	{
		if(v[i]==0)
		{
			v[i]=cad[2].second;
		}
	}
	return v;
}

Compilation message (stderr)

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

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