Submission #200931

#	Time	Username	Problem	Language	Result	Execution time	Memory
200931		Lawliet	Split the Attractions (IOI19_split)	C++17	29 / 100	591 ms	1048576 KiB

split

#include <bits/stdc++.h>
#include "split.h"

using namespace std;

const int MAXN = 100010;

int n;

int pai[MAXN];
int sub[MAXN];
int type[MAXN];

vector< int > ans;

vector< int > adj[MAXN];

void DFS(int cur, int p)
{
	sub[cur] = 1;
	pai[cur] = p;

	for(int i = 0 ; i < adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];

		if( viz == p ) continue;

		DFS( viz , cur );

		sub[ cur ] += sub[ viz ];
	}
}

void findAnswer(int cur, int blocked, int& qtd, int t)
{
	if( qtd == 0 ) return;

	qtd--;
	type[ cur ] = t;

	for(int i = 0 ; i < adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];

		if( viz == blocked ) continue;
		if( viz == pai[cur] ) continue;

		findAnswer( viz , blocked , qtd , t );
	}
}

void tryAnswer(int A, int tA, int B, int tB)
{
	if( ans.size() > 0 ) return;

	bool find = false;

	for(int i = 1 ; i < n && !find ; i++)
	{
		int other = n - sub[i];

		if( sub[i] >= A && other >= B )
		{
			find = true;

			findAnswer( 0 , i , B , tB );
			findAnswer( i , pai[i] , A , tA );			
		}
	}

	if( !find ) return;

	for(int i = 0 ; i < n ; i++)
	{
		if( type[i] != 0 ) ans.push_back( type[i] );
		else ans.push_back( 6 - tA - tB );
	}
}

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

	for(int i = 0 ; i < N - 1 ; i++)
	{
		adj[ p[i] ].push_back( q[i] );
		adj[ q[i] ].push_back( p[i] );
	}

	DFS( 0 , 0 );

	tryAnswer( a , 1 , b , 2 );
	tryAnswer( a , 1 , c , 3 );
	tryAnswer( b , 2 , a , 1 );
	tryAnswer( b , 2 , c , 3 );
	tryAnswer( c , 3 , a , 1 );
	tryAnswer( c , 3 , b , 2 );

	if( ans.size() == 0 ) ans.resize( n , 0 );

	return ans;
}

Compilation message (stderr)

split.cpp: In function 'void DFS(int, int)':
split.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
split.cpp: In function 'void findAnswer(int, int, int&, int)':
split.cpp:42:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~

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