oj.uz

Submission #313953

# Submission time Handle Problem Language Result Execution time Memory
313953 2020-10-17T14:57:00 Z CaroLinda Amusement Park (JOI17_amusement_park) C++14
10 / 100
 107 ms 6160 KB 
#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 ;

	}

}

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

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

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

		if( group[e] == searchGroup  && e != father[x] && !mark[e] )
			dfs2(e, qtd, searchGroup ) ;
	}

	if(qtd <= 0) return ;

	if(!mark[father[x]])
		dfs2(father[x] , qtd, searchGroup ) ;

}

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 
		{
			int qtd = 60 - sub[x] ;
			for(int i = 0 ; i < 60 ; i++ ) freq[i] = false ;

			dfs2( father[x] , qtd, group[ 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) ) ;

}

#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 ;

	}

}

void dfs22(int x, int &qtd , int searchGroup )
{
	if(qtd <= 0) return ;

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

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

		if( grupo[e] == searchGroup && e != pai[x] && !vis[e] )
			dfs22(e, qtd, searchGroup ) ;
	}

	if(qtd <= 0) return ;

	if(!vis[pai[x]])
		dfs22(pai[x] , qtd, searchGroup ) ;

}

int qtd = 60 ;
void dfsTraversal(int x)
{
	vis[x] = true ;
	qtd-- ;

	if(qtd == 0 ) return ;

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

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

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

	}

	if(x == 0 || qtd <= 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 
		{
			int qtd = 60 - subarvore[x] ;
			for(int i = 0 ; i < 60 ; i++ ) frequencia[i] = false ;

			dfs22( pai[x] , qtd, grupo[ 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1820 KB Output is correct
2 Correct 2 ms 1672 KB Output is correct
3 Incorrect 2 ms 1944 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6160 KB Output is correct
2 Incorrect 34 ms 6140 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1808 KB Output is correct
2 Correct 2 ms 1800 KB Output is correct
3 Correct 2 ms 1672 KB Output is correct
4 Correct 4 ms 2356 KB Output is correct
5 Correct 4 ms 2592 KB Output is correct
6 Correct 4 ms 2356 KB Output is correct
7 Correct 4 ms 2584 KB Output is correct
8 Correct 4 ms 2484 KB Output is correct
9 Correct 19 ms 5764 KB Output is correct
10 Correct 17 ms 5548 KB Output is correct
11 Correct 17 ms 5624 KB Output is correct
12 Correct 2 ms 1820 KB Output is correct
13 Correct 2 ms 1800 KB Output is correct
14 Correct 2 ms 1816 KB Output is correct
15 Correct 2 ms 1808 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 6052 KB Output is correct
2 Correct 36 ms 5952 KB Output is correct
3 Incorrect 35 ms 6052 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 6152 KB Output is correct
2 Correct 34 ms 6052 KB Output is correct
3 Correct 34 ms 6152 KB Output is correct
4 Correct 23 ms 4472 KB Output is correct
5 Correct 20 ms 5328 KB Output is correct
6 Correct 22 ms 4884 KB Output is correct
7 Correct 20 ms 4668 KB Output is correct
8 Correct 22 ms 4796 KB Output is correct
9 Correct 22 ms 4856 KB Output is correct
10 Correct 107 ms 4812 KB Output is correct
11 Correct 98 ms 4820 KB Output is correct
12 Correct 19 ms 4380 KB Output is correct
13 Incorrect 19 ms 4224 KB Wrong Answer [7]
14 Halted 0 ms 0 KB -