Submission #198417

#	Time	Username	Problem	Language	Result	Execution time	Memory
198417		FerThugGato12500	Split the Attractions (IOI19_split)	C++14	0 / 100	11 ms	5548 KiB

split

#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#include<split.h>
using namespace std;
vector<int> ed[100001];
int need[3];
int n, m;
bool vis[100001];
int cld[100001];
int dfs(int ind)
{
	int D=1;
	vis[ind]=true;
	for(int i = 0; i < ed[ind].size(); i++)
		if(!vis[ed[ind][i]])
			D+=dfs(ed[ind][i]);
	return (cld[ind] = D);
}
int bus(int ind)
{
	bool z=true;
	vis[ind]=true;
	for(int i = 0; i < ed[ind].size(); i++)
		if(!vis[ed[ind][i]] && cld[ed[ind][i]]>=n/2)
			z=false;
	if(n-cld[ind]>=n/2)
		z=false;
	if(z) return ind;
	int D=-1;
	for(int i = 0; i < ed[ind].size(); i++)
		if(!vis[ed[ind][i]])
			D=max(bus(ed[ind][i]), D);
	return D;
}
int centroide()
{
	dfs(1);
	memset(vis, false, sizeof(vis));
	return bus(1);
}
vector<int> ans[3];
int rey;
typedef struct 
{
	int to, cld;
}Wasd;
bool operator < (const Wasd &a, const Wasd &b)
{
	return a.cld < b.cld;
}
void expand(int ind)
{
	vis[ind]=true;
	ans[rey].push_back(ind);
	if(ans[rey].size()==need[rey])
		return;
	vector<Wasd> ed2;
	Wasd te;
	for(int i = 0; i < ed[ind].size(); i++)
	{
		te.to=ed[ind][i];
		te.cld=cld[te.to]-cld[ind];
		if(te.cld<0) te.cld=cld[te.to];
		ed2.push_back(te);
	}
	sort(ed2.begin(), ed2.end());
	for(int i = 0; i < ed2.size(); i++)
		if(!vis[ed2[i].to] && ans[rey].size()<need[rey])
			expand(ed2[i].to);
	return;
}
int res[100001];
vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q)
{
	n=N; need[0]=a; need[1]=b; need[2]=c;
	m=p.size();
	int x, y;
	for(int i = 0; i < m; i++)
	{
		x=p[i]; y=q[i];
		ed[x].push_back(y);
		ed[y].push_back(x);
	}
	int cnt = centroide();
	if(need[0]<=max(need[1], need[2]) && need[0]>=min(need[2], need[1]))
		rey=0;
	else if(need[1]<=max(need[0], need[2]) && need[1]>=min(need[2], need[0]))
		rey=1;
	else rey=2;
	memset(vis, false, sizeof(vis));
	expand(cnt);
	if(need[0]<=need[1] && need[0]<=need[2])
		rey=0;
	else if(need[1]<=need[0] && need[1]<=need[2])
		rey=1;
	else rey=2;
	for(int i = 0; i < n; i++)
		if(!vis[i])
		{
			expand(i);
			if(ans[rey].size()==need[rey])
				break;
			ans[rey].clear();
		}
	for(int k = 0; k < 3; k++)
		for(int i = 0; i < ans[k].size(); i++)
			res[ans[k][i]]=k+1;
	if(ans[0].size()>0 && ans[1].size()>0)
		rey=2;
	else if(ans[1].size()>0 && ans[2].size()>0)
		rey=0;
	else rey=1;
	for(int i = 0; i < n; i++)
		if(res[i]==0)
			res[i] = rey+1;
	vector<int> respuesta;
	for(int i = 0; i < n; i++)
		respuesta.push_back(res[i]);
	return respuesta;
}

Compilation message (stderr)

split.cpp: In function 'int dfs(int)':
split.cpp:16:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ed[ind].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
split.cpp: In function 'int bus(int)':
split.cpp:25:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ed[ind].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
split.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ed[ind].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
split.cpp: In function 'void expand(int)':
split.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(ans[rey].size()==need[rey])
     ~~~~~~~~~~~~~~~^~~~~~~~~~~
split.cpp:61:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ed[ind].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
split.cpp:69:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ed2.size(); i++)
                 ~~^~~~~~~~~~~~
split.cpp:70:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(!vis[ed2[i].to] && ans[rey].size()<need[rey])
                         ~~~~~~~~~~~~~~~^~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:103:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ans[rey].size()==need[rey])
       ~~~~~~~~~~~~~~~^~~~~~~~~~~
split.cpp:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < ans[k].size(); i++)
                  ~~^~~~~~~~~~~~~~~

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