Submission #294843

#	Time	Username	Problem	Language	Result	Execution time	Memory
294843		Fasho	Split the Attractions (IOI19_split)	C++14	11 / 100	136 ms	20728 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
using namespace std;
#include "split.h"

using namespace std;

ll nn,mm,x,y,z,flag,mark[N];
vector<int> v[N],ans(nn);

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);
	}

}

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);
	}
	if(b>c)
		flag=1;
	// cerr<<ans.size()<<endl;
	ans.resize(nn);
	fo(i,0,nn-1)
		if(v[i].size()<2)
			rt=i;
	f(rt,rt);
	for(int i=0;i<nn;i++)
	{
		if(ans[i]==0)
		{
			if(x)
			{
				x--;
				ans[i]=1;
			}
			else if(flag)
				ans[i]=2;
			
			else
				ans[i]=3;
		}
	}
	return ans;



}

// int main() {
// 	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 'void f(int, int)':
split.cpp:57:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for(int i=0;i<v[ind].size();i++)
      |              ~^~~~~~~~~~~~~~

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