Submission #152870

#	Time	Username	Problem	Language	Result	Execution time	Memory
152870		tinjyu	Split the Attractions (IOI19_split)	C++14	0 / 100	2 ms	376 KiB

split

#include "split.h"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h> 
using namespace std;
long long int cnt=0,x1[100005],y1[100005],can=0,ans[100005],f[100005],s,e,stop,a[2],b[2],c[2],sum[100005],t[100005],n,m,road[100005],map[1000005][2],tag[100005];
int buildp(int x,int father)
{
	tag[x]=1;
	f[x]=father;
	sum[x]=1;
	int g=road[x];
	while(g!=-1)
	{
		int now=map[g][0];
		if(tag[now]==0)sum[x]+=buildp(now,x);
		g=map[g][1];
	}
	return sum[x];
}
int color(int x,int col)
{
	if(s==e)return 0;
	s++;
	ans[x]=col;
	int g=road[x];
	while(g!=-1)
	{
		if(s==e)return 0;
		int now=map[g][0];
		if(now!=f[x] && now!=stop)color(now,col);
		g=map[g][1];
	}
}
int find(int x,int father)
{
	if(sum[x]>=a[0] && father>=b[0])
	{	
		can=1;
		stop=f[x];
		s=0;
		e=a[0];
		color(x,a[1]);
		stop=x;
		s=0;
		e=b[0];
		color(0,b[1]);
		return 0;
	}
	if(father>=a[0] && sum[x]>=b[0])
	{
		can=1;
		stop=x;
		s=0;
		e=a[0];
		color(0,a[1]);
		stop=f[x];
		s=0;
		e=b[0];
		color(x,b[1]);
		return 0;
	}
	int g=road[x];
	while(g!=-1)
	{
		int now=map[g][0];
		if(now!=f[x])find(now,father+(sum[x]-sum[now]));
		if(can==1)return 0;
		g=map[g][1];
	}
}
int dfs(int x)
{
	int g=road[x];
	tag[x]=1;
	while(g!=-1)
	{
		int now=map[g][0];
		if(tag[now]==0)
		{
			y1[cnt]=x;
			x1[cnt]=now;
			cnt++;
			dfs(now);
		}
		g=map[g][1];
	}
	return 0;
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
	a[0]=A;
	a[1]=1;
	b[0]=B;
	b[1]=2;
	c[0]=C;
	c[1]=3;
	srand (time(NULL));

	if(b[0]<=a[0] && b[0]<=c[0])
	{
		swap(a[0],b[0]);
		swap(a[1],b[1]);
	}
	if(c[0]<=b[0] && c[0]<=a[0])
	{
		swap(a[0],c[0]);
		swap(a[1],c[1]);
	}
	if(c[0]<=b[0])
	{
		swap(b[0],c[0]);
		swap(b[1],c[1]);
	}
	n=N;
	m=q.size();
	for(int i=0;i<=n;i++)road[i]=-1;
	for(int i=0;i<m;i++)
	{
		map[i*2][0]=p[i];
		map[i*2][1]=road[q[i]];
		road[q[i]]=i*2;
		map[i*2+1][0]=q[i];
		map[i*2+1][1]=road[p[i]];
		road[p[i]]=i*2+1;
	}
	int qw=0;
	while(qw<n)
	{
		dfs(qw);
		for(int i=0;i<=n;i++)
		{
			road[i]=-1;
			tag[i]=0;
		}
		cnt=0;
		for(int i=0;i<cnt;i++)
		{
			map[i*2][0]=x1[i];
			map[i*2][1]=road[y1[i]];
			road[y1[i]]=i*2;
			map[i*2+1][0]=y1[i];
			map[i*2+1][1]=road[x1[i]];
			road[x1[i]]=i*2+1;
		}
		can=0;
		for(int i=0;i<n;i++)sum[i]=0;
		buildp(0,-1);
		find(0,0);
		
		if(can==1)
		{
			vector<int> res(n);
			for(int i=0;i<n;i++)
			{
				res[i]=ans[i];
				if(res[i]==0)res[i]=c[1];
			} 
			return res;
		}
		qw++;
	}
	vector<int> res(n);
}

Compilation message (stderr)

split.cpp: In function 'int color(int, int)':
split.cpp:35:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
split.cpp: In function 'int find(int, int)':
split.cpp:72:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:164:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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