Submission #295013

#	Time	Username	Problem	Language	Result	Execution time	Memory
295013		Fasho	Split the Attractions (IOI19_split)	C++14	40 / 100	160 ms	29048 KiB

split

#include <algorithm>
#include <iostream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define N 500005
#define ll long long int
#define fo(i,x,y) for(int i=x;i<=y;i++)
#define fs(ar,n) fo(i,1,n) cin>>ar[i]
#define sp " "
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll> 
#define fast2 freopen ("in.txt","r",stdin);freopen ("out.txt","w",stdout);
#define inf 1000000000
#define MP make_pair
using namespace std;
#include "split.h"

using namespace std;
lli pp[N];
ll nn,mm,x,y,z,flag,mark[N],tut[N],tt[N];
vector<int> v[N],ans(nn);


ll f1(int ind,int back)
{
	if(mark[ind])
		return 0;
	tt[ind]=back;
	mark[ind]++;
	ll top=1;
	for(int i=0;i<v[ind].size();i++)
	{
		ll xx=v[ind][i];
		if(mark[xx])
			continue;
		top+=f1(xx,ind);
	}
	return tut[ind]=top;

}

void f(int ind,int back)
{
	// cerr<<ind<<endl;
	if(mark[ind])
		return;
	mark[ind]++;

	if(flag && !z)
		return;
	if(!flag && !y)
		return;
	
	if(!flag && y)
		ans[ind]=2,y--;
	if(flag && z)
		ans[ind]=3,z--;
	for(int i=0;i<v[ind].size();i++)
	{
		int xx=v[ind][i];
		if(xx!=back)
			f(xx,ind);
	}

}
void f2(int ind,int back)
{
	if(mark[ind] || !pp[1].fi)
		return;
	mark[ind]=1;
	pp[1].fi--;
	ans[ind]=pp[1].se;
	for(int i=0;i<v[ind].size();i++)
	{
		ll xx=v[ind][i];
		if(mark[xx] || back==xx)
			continue;
		f2(xx,ind);
	}
}
void f3(int ind,int back)
{
	if(mark[ind] || !pp[2].fi)
		return;
	mark[ind]=1;
	pp[2].fi--;
	ans[ind]=pp[2].se;
	for(int i=0;i<v[ind].size();i++)
	{
		ll xx=v[ind][i];
		if(mark[xx] || back==xx)
			continue;
		f3(xx,ind);
	}
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	mm=p.size();
	nn=n;
	x=a;
	y=b;
	z=c;

	int rt=0;
	fo(i,0,mm-1)
	{
		int at=p[i];
		int bt=q[i];
		v[at].pb(bt);
		v[bt].pb(at);
	}
	pp[1]=MP(a,1);
	pp[2]=MP(b,2);
	pp[3]=MP(c,3);
	sort(pp+1,pp+4);
	if(b>c)
		flag=1;
	// cerr<<ans.size()<<endl;
	ans.resize(nn);
	fo(i,0,nn-1)
		if(v[i].size()<2)
			rt=i;
	f1(rt,rt);
	memset(mark,0,sizeof(mark));
	for(int i=0;i<n;i++)
	{
		// cout<<i<<sp<<tut[i]<<sp<<tt[i]<<endl;
		if(tut[i]>=pp[1].fi && n-tut[i]>=pp[2].fi)
		{
			f2(i,tt[i]);
			f3(tt[i],i);
			for(int j=0;j<n;j++)
				if(ans[j]==0)
				{
					int xxx=pp[3].se;

					ans[j]=xxx;
				}
				// cerr<<" HELLO"<<sp<<i<<endl;
			break;
		}
		else if(tut[i]>=pp[2].fi && n-tut[i]>=pp[1].fi)
		{
			f3(i,tt[i]);
			f2(tt[i],i);
			for(int j=0;j<n;j++)
				if(ans[j]==0)
				{
					int xxx=pp[3].se;

					ans[j]=xxx;
				}
				// cerr<<" HELLO"<<sp<<i<<endl;
			break;

		}
	}
	return ans;



}

// int main() {
// 	fast2;
// 	int n, m, a, b, c;
// 	assert(5 == scanf("%d%d%d%d%d", &n, &m, &a, &b, &c));
// 	vector<int> p(m), q(m);
// 	for (int i=0; i<m; i++)
// 		assert(2 == scanf("%d%d", &p[i], &q[i]));
// 	fclose(stdin);

// 	vector<int> result = find_split(n, a, b, c, p, q);

// 	for (int i=0; i<(int)result.size(); i++)
// 		printf("%s%d", ((i>0)?" ":""), result[i]);
// 	printf("\n");
// 	fclose(stdout);
// 	return 0;
// }

Compilation message (stderr)

split.cpp: In function 'long long int f1(int, int)':
split.cpp:50:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for(int i=0;i<v[ind].size();i++)
      |              ~^~~~~~~~~~~~~~
split.cpp: In function 'void f(int, int)':
split.cpp:77:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int i=0;i<v[ind].size();i++)
      |              ~^~~~~~~~~~~~~~
split.cpp: In function 'void f2(int, int)':
split.cpp:92:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for(int i=0;i<v[ind].size();i++)
      |              ~^~~~~~~~~~~~~~
split.cpp: In function 'void f3(int, int)':
split.cpp:107:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |  for(int i=0;i<v[ind].size();i++)
      |              ~^~~~~~~~~~~~~~

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