Submission #199194

#	Time	Username	Problem	Language	Result	Execution time	Memory
199194		FerThugGato12500	Split the Attractions (IOI19_split)	C++14	40 / 100	195 ms	17892 KiB

split

#include "split.h"
#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
bool vis[100001];
bool mark[100001];
bool used[100001];
int ch[2][100001];
int ex[2][100001];
bool z;
typedef struct 
{
	int t, ind;
}An;
queue<An> bfs;
int n, m, q;
vector<int> ed[100001];
vector<int> fb[100001];
void extend(int ind)
{
	An te, ta;
	te.ind=ind; te.t=1;
	bfs.push(te);
	int bg=-1;
	vis[ind]=true;
	while(bfs.size()>0)
	{
		te=bfs.front(); bfs.pop();
		bg=max(bg, te.t);
		ex[z][te.ind]=te.t;
		fb[te.t].push_back(te.ind);
		for(int i = 0; i < ed[te.ind].size(); i++)
			if(!vis[ed[te.ind][i]])
			{
				vis[ed[te.ind][i]]=true;
				ta.ind=ed[te.ind][i];
				ta.t=te.t+1;
				bfs.push(ta);
			}
	}
	for(int i = bg; i > 0; i--)
	{
		for(int k = 0; k < fb[i].size(); k++)
		{
			int D=1;
			int ind=fb[i][k];
			for(int j = 0; j < ed[ind].size(); j++)
				if(!mark[ed[ind][j]] && ex[z][ed[ind][j]]>i)
				{
					mark[ed[ind][j]]=true;
					D+=ch[z][ed[ind][j]];
				}
			ch[z][ind]=D;
		}
	}
	return;
}
int N, r;
void busca(int ind)
{
	bool c=true;
	used[ind]=true;
	for(int i = 0; i < ed[ind].size(); i++)
		if(!used[ed[ind][i]] && ch[z][ed[ind][i]]>N)
		{ c=false; break; }
	if(c && n-ch[z][ind]<N)
	{ r=ind; return; }
	for(int i = 0; i < ed[ind].size(); i++)
		if(!used[ed[ind][i]] && r==-1)
			busca(ed[ind][i]);
	return;
}
typedef struct 
{
	int ind, nd;
}Wasd;
bool operator < (const Wasd &a, const Wasd &b)
{
	return a.nd<b.nd;
}
Wasd need[3];
typedef struct 
{
	int ind, ch;
}Re;
bool operator < (const Re &a, const Re &b)
{
	return a.ch>b.ch;
}
priority_queue<Re> mqun;
int ans[100001];
int it;
int esaq[100001];
void poder(int ind)
{
	if(r==need[0].nd)
		return;
	r++;
	esaq[ind]=it;
	if(z) ans[ind]=need[0].ind;
	for(int i = 0; i < ed[ind].size(); i++)
		if(!vis[ed[ind][i]] && esaq[ed[ind][i]]!=it && r<need[0].nd)
			poder(ed[ind][i]);
	return;
}
vector<int> find_split(int s, int a, int b, int c, vector<int> p, vector<int> q)
{
	n = s; m=p.size(); 
	need[0].nd = a; need[1].nd = b; need[2].nd = c;
	need[0].ind=1; need[1].ind=2; need[2].ind=3;
	sort(need, need+3);
	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);
	}
	z=0;
	extend(0);
	N=(n+1)/2;
	r=-1;
	busca(0);
	int centroide=r;
	memset(vis, false, sizeof(vis));
	memset(mark, false, sizeof(mark));
	for(int i = 0; i < 100001; i++)
		fb[i].clear();
	z=1;
	extend(centroide);
	Re te, ta;
	ta.ch=ch[1][centroide]; 
	ta.ind=centroide;
	mqun.push(ta);
	memset(vis, false, sizeof(vis));
	int D=0;
	while(D<need[1].nd)
	{
		ta=mqun.top(); mqun.pop();
		if(!vis[ta.ind])
		{
			D++;
			vis[ta.ind]=true;
			ans[ta.ind]=need[1].ind;
			for(int i = 0; i < ed[ta.ind].size(); i++)
				if(!vis[ed[ta.ind][i]])
				{
					te.ind=ed[ta.ind][i];
					te.ch=ch[1][ed[ta.ind][i]];
					mqun.push(te);
				}
		}
	}
	z=false;
	for(int i = 0; i < ed[centroide].size(); i++)
		if(ans[ed[centroide][i]]==0)
		{
			r=0;
			it++;
			poder(ed[centroide][i]);
			if(r==need[0].nd)
			{
				r=0;
				it++;
				z=true;
				poder(ed[centroide][i]);
				break;
			}
		}
	vector<int> res;
	if(!z)
	{
		for(int i = 0; i < n; i++)
			res.push_back(0);
		return res;
	}
	for(int i = 0; i < n; i++)
		if(ans[i]==0)
			res.push_back(need[2].ind);
		else res.push_back(ans[i]);
	return res;
}

Compilation message (stderr)

split.cpp: In function 'void extend(int)':
split.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < ed[te.ind].size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~
split.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k = 0; k < fb[i].size(); k++)
                  ~~^~~~~~~~~~~~~~
split.cpp:50:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0; j < ed[ind].size(); j++)
                   ~~^~~~~~~~~~~~~~~~
split.cpp: In function 'void busca(int)':
split.cpp:66:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ed[ind].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
split.cpp:71: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 poder(int)':
split.cpp:104:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ed[ind].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:148:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < ed[ta.ind].size(); i++)
                   ~~^~~~~~~~~~~~~~~~~~~
split.cpp:158:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ed[centroide].size(); i++)
                 ~~^~~~~~~~~~~~~~~~~~~~~~

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