Submission #313954

#	Time	Username	Problem	Language	Result	Execution time	Memory
313954		CaroLinda	Amusement Park (JOI17_amusement_park)	C++14	100 / 100	37 ms	6156 KiB

Joi

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

#define sz(x) (int)(x.size())
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define ll long long
#define pii pair<int,int>

const int MAXN = 1e4+10 ;

using namespace std ;

int val[MAXN] , sub[MAXN] ;
int ini[MAXN] , fim[MAXN] ;
int group[MAXN] , father[MAXN] ;
vector<int> adj[MAXN] ;
vector<int> tree[MAXN] ;
bool freq[65] ;
bool mark[MAXN] ;

void dfs1(int x)
{
	sub[x] = 1 ;

	for(auto e : adj[x] ) 
	{
		if( sub[e] > 0) continue ;

		dfs1(e) ;

		tree[x].push_back(e) ;
		sub[x] += sub[e] ;

		tree[e].push_back(x) ;
		father[e] = x ;

	}

}

int qtd ;
void dfs2(int x)
{
	if(qtd <= 0) return ;

	freq[ val[x] ] = true ;
	qtd-- ;

	for(auto e : tree[x] ) 
	{
		if(qtd <= 0) return ;

		if( group[e] == group[x]  && e != father[x] && !freq[ val[e] ] )
			dfs2(e) ;
	}

	if(qtd <= 0) return ;

	if(!freq[val[father[x]]])
		dfs2(father[x]) ;

}

int isOn(int i, ll x ) { return ((1LL<<i)&x) != 0; }

void Joi(int N, int M, int A[], int B[], long long X, int T) 
{

	for(int i = 0 ; i < N ; i++ ) val[i] = -1 ;
	father[0] = -1 ;

	for(int i= 0 ; i < M ; i++ ) 
	{
		adj[ A[i] ].push_back( B[i] ) ;
		adj[ B[i] ].push_back( A[i] ) ;
	}

	dfs1(0) ;

	vector<int> fila(1,0) ;
	int ini = 0 ; 

	while( ini < sz(fila) )
	{
		int x = fila[ini++] ;

		vector<int> miniFila(1,x) ;
		int miniIni = 0 ;

		if( sub[x] >= 60 )
		{

			while(miniIni < sz(miniFila) && miniIni < 60 )
			{
				int miniX = miniFila[miniIni] ;
				val[ miniX ] = miniIni++ ;
				group[miniX] = -(x+1) ;

				for(auto e : tree[miniX] ) 
					if(val[e] == -1)
						miniFila.push_back(e) ;
			}

			for(int i = miniIni ; i < sz(miniFila) ; i++ ) 
				fila.push_back(miniFila[i]) ;
		}
		else 
		{
			qtd = 60 - sub[x] ;
			for(int i = 0 ; i < 60 ; i++ ) freq[i] = false ;

			dfs2( father[x] ) ;

			while(miniIni < sz(miniFila))
			{
				int miniX = miniFila[miniIni++] ;
				group[miniX] = x+1 ;

				for(int i = 0 ; i < 60 ; i++ )
					if(freq[i] == false )
					{
						freq[i] = true ;
						val[ miniX ] = i ;
						break ;
					}

				for(auto e : tree[miniX] ) 
					if(val[e] == -1)
						miniFila.push_back(e) ;
			}

		}

	}

	//for(int i = 0 ;i < N ; i++ ) cout << val[i] << endl ;

  	for(int i = 0 ; i < N ; i++ ) 
  		MessageBoard( i, isOn(val[i] , X) ) ;

}

Ioi

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

#define debug printf
#define sz(x) (int)(x.size())
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define ll long long

const int MAX = 1e4+10 ;

using namespace std ;

int valor[MAX] , subarvore[MAX ] ;
int pai[MAX] , grupo[MAX] ;
int achei[65] ;
bool frequencia[65] ;
bool vis[MAX] ;
vector<int> graph[MAX] , arvore[MAX] ;

void dfs11(int x)
{
	subarvore[x] = 1 ;

	for(auto e : graph[x] ) 
	{
		if( subarvore[e] > 0) continue ;

		dfs11(e) ;

		arvore[x].push_back(e) ;
		subarvore[x] += subarvore[e] ;

		arvore[e].push_back(x) ;
		pai[e] = x ;

	}

}

int quantidade ;
void dfs22(int x)
{
	if(quantidade <= 0) return ;

	frequencia[ valor[x] ] = true ;
	quantidade-- ;

	for(auto e : arvore[x] ) 
	{
		if(quantidade <= 0) return ;

		if( grupo[e] == grupo[x] && e != pai[x] && !frequencia[valor[e]] )
			dfs22(e) ;
	}

	if(quantidade <= 0) return ;

	if(!frequencia[valor[pai[x]]])
		dfs22(pai[x] ) ;

}

int qtdd = 60 ;
void dfsTraversal(int x)
{
	if(qtdd <= 0 ) return ;

	vis[x] = true ;
	qtdd-- ;

	for(auto e : arvore[x])
	{
		if(qtdd <= 0 ) return;

		if(e == pai[x] || grupo[e] != grupo[x] || vis[e] )  continue ;

		achei[ valor[e] ] = Move(e);
		dfsTraversal(e) ;

	}

	if(x == 0 || qtdd <= 0 ) return ;

	achei[ valor[ pai[x] ] ] = Move(pai[x]) ;

	if(!vis[ pai[x] ])
		dfsTraversal(pai[x]) ;

}

long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) 
{

	for(int i = 0 ; i < N ; i++ ) valor[i] = -1 ;
	pai[0] = -1 ;

	for(int i= 0 ; i < M ; i++ ) 
	{
		graph[ A[i] ].push_back( B[i] ) ;
		graph[ B[i] ].push_back( A[i] ) ;
	}

	dfs11(0) ;

	vector<int> fila(1,0) ;
	int ini = 0 ; 

	while( ini < sz(fila) )
	{
		int x = fila[ini++] ;

		vector<int> miniFila(1,x) ;
		int miniIni = 0 ;

		if( subarvore[x] >= 60 )
		{

			while(miniIni < sz(miniFila) && miniIni < 60 )
			{
				int miniX = miniFila[miniIni] ;
				valor[ miniX ] = miniIni++ ;
				grupo[miniX] = -(x+1) ;

				for(auto e : arvore[miniX] ) 
					if(valor[e] == -1)
						miniFila.push_back(e) ;
			}

			for(int i = miniIni ; i < sz(miniFila) ; i++ ) 
				fila.push_back(miniFila[i]) ;
		}
		else 
		{
			quantidade = 60 - subarvore[x] ;
			for(int i = 0 ; i < 60 ; i++ ) frequencia[i] = false ;

			dfs22( pai[x] );

			while(miniIni < sz(miniFila))
			{
				int miniX = miniFila[miniIni++] ;
				grupo[miniX] = x+1 ;

				for(int i = 0 ; i < 60 ; i++ )
					if(frequencia[i] == false )
					{
						frequencia[i] = true ;
						valor[ miniX ] = i ;
						break ;
					}

				for(auto e : arvore[miniX] ) 
					if(valor[e] == -1)
						miniFila.push_back(e) ;
			}

		}

	}

	achei[ valor[P] ] = V ;

	for(int i = 0 ; i< N ; i++ ) vis[i] = false ;

	dfsTraversal(P) ;

	ll resp = 0LL ;
	for(int i = 0 ;i < 60 ; i++ )
		resp += (1LL<<i) * achei[i] ;

	return resp ;

}

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17