oj.uz

Submission #313733

# Submission time Handle Problem Language Result Execution time Memory
313733 2020-10-16T20:51:46 Z CaroLinda Amusement Park (JOI17_amusement_park) C++14
10 / 100
 40 ms 4640 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

using namespace std ;

vector<int> ordem ;
vector< vector<int> > adj ;
vector<bool> vis ;

void dfs(int x)
{
	vis[x] = true ;
	ordem.push_back(x) ;

	for(auto e : adj[x])
	{
		
		if(vis[e]) continue ;

		dfs(e) ;
		ordem.push_back(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) 
{

	adj.resize( N+10 , vector<int>() )	 ;
	vis.resize(N+10,false) ;

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

	for(int i = 0 ; i < N ; i++ ) sort(all(adj[i]));

	dfs(0) ;

	vector<int> freq(60, 0) ;
  	vector<int> val(N+10, -1) ;

  	set<int> holdingOn ;

  for(int i = 0 ; i < sz(ordem) ; i++ )
  {
  	if( i-121 >= 0 && val[ordem[i-121]]!= -1 && (--freq[ val[ordem[i-121]] ]) == 0 && sz(holdingOn) > 0)
  	{
  		int x = *holdingOn.begin() ;
  		holdingOn.erase( holdingOn.begin() ) ;

  		val[x] = val[ordem[i-121]] ;

  		for(int j = i-120 ; j <= i ; j++ )
  			if( ordem[j] == x ) freq[ val[x] ]++ ;

  	}


  	if(val[ ordem[i] ] == -1)
  	{
  		for(int j = 0 ; j < 60 ; j++ )
  			if(freq[j] == 0) 
  			{
  				val[ ordem[i] ] = j ;
  				break ;
  			}

  		if( val[ordem[i]] == -1 ) holdingOn.insert(ordem[i]) ;
  		else if( holdingOn.find(ordem[i]) != holdingOn.end() )
  			holdingOn.erase( holdingOn.find(ordem[i]) ) ;
  	}

  	if( val[ordem[i]] != -1 )
  		freq[ val[ ordem[i] ] ]++ ;

  }	

  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

using namespace std ;

vector<int> ord , tin , tout ;
vector< vector<int> > graph ;
vector<bool> mark ;

void dfsPrime(int x)
{
	tin[x] = tout[x] = sz(ord);
	mark[x] = true ;

	ord.push_back(x) ;

	for(auto e : graph[x])
	{
		if(mark[e]) continue ;
		
		dfsPrime(e) ;

		tout[x] = sz(ord) ;
		ord.push_back(x) ;
	}

}

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

	graph.resize( N+10 , vector<int>() );
	tin.resize(N+10);
	tout.resize(N+10) ;
	mark.resize(N+10,false) ;

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

	for(int i = 0 ; i < N ; i++ ) sort(all(graph[i]));

	dfsPrime(0) ;

	vector<int> freq(60, 0) ;
  	vector<int> val(N+10, -1) ;

  	set<int> holdingOn ;

  for(int i = 0 ; i < sz(ord) ; i++ )
  {
  	if( i-121 >= 0 && val[ord[i-121]]!= -1 && (--freq[ val[ord[i-121]] ]) == 0 && sz(holdingOn) > 0)
  	{
  		int x = *holdingOn.begin() ;
  		holdingOn.erase( holdingOn.begin() ) ;

  		val[x] = val[ord[i-121]] ;

  		for(int j = i-120 ; j <= i ; j++ )
  			if( ord[j] == x ) freq[ val[x] ]++ ;

  	}

  	if(val[ ord[i] ] == -1)
  	{
  		for(int j = 0 ; j < 60 ; j++ )
  			if(freq[j] == 0) 
  			{
  				val[ ord[i] ] = j ;
  				break ;
  			}

  		if( val[ord[i]] == -1 ) holdingOn.insert(ord[i]) ;
  		else if( holdingOn.find(ord[i]) != holdingOn.end() )
  			holdingOn.erase( holdingOn.find(ord[i]) ) ;
  	}

  	if( val[ord[i]] != -1 )
  		freq[ val[ ord[i] ] ]++ ;

  }	

  int ptrBeg , ptrEn ;

  for(int i = 0 ; i < sz(ord) ; i++ )
  	if(ord[i] == P) { ptrBeg = ptrEn = i ; break ; }

  vector<int> achei(60,0) ;
  achei[ val[P] ] = V ;

  int qtd = 150 ;

  while(qtd--)
  {
  	//cout << ptrBeg << " " << ptrEn << " " << qtd <<  " " << tin[P]<<" " << tout[P] << " " << P << endl ;

  	if( ptrBeg == tin[P] && ptrEn == tout[P] )
	{
		if(ptrBeg == 0 || ptrEn+1 == sz(ord)) break ;

		P = ord[ptrBeg-1] ;

		achei[ val[P] ] = Move(P) ;
		
		ptrBeg-- ;
		ptrEn++ ;

	}  
	else 
	{
		if( ptrBeg > tin[P]  )
		{
			achei[ val[ ord[ptrBeg-1] ] ] = Move(ord[ptrBeg-1]) ;
			ptrBeg-- ;
		}
		else 
		{
			achei[ val[ord[ptrEn+1]] ] = Move(ord[ptrEn+1]);
			ptrEn++ ;
		}
	}

  }

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

  return x ;

}

Compilation message

Ioi.cpp: In function 'long long int Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:108:26: warning: 'ptrEn' may be used uninitialized in this function [-Wmaybe-uninitialized]
  108 |   if(ptrBeg == 0 || ptrEn+1 == sz(ord)) break ;
      |                     ~~~~~^~
Ioi.cpp:122:51: warning: 'ptrBeg' may be used uninitialized in this function [-Wmaybe-uninitialized]
  122 |    achei[ val[ ord[ptrBeg-1] ] ] = Move(ord[ptrBeg-1]) ;
      |                                             ~~~~~~^~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 900 KB Output is correct
2 Correct 1 ms 772 KB Output is correct
3 Correct 2 ms 996 KB Output is correct
4 Correct 1 ms 1008 KB Output is correct
5 Correct 2 ms 1012 KB Output is correct
6 Incorrect 2 ms 1004 KB Wrong Answer [7]
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 4452 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 900 KB Output is correct
2 Correct 1 ms 1008 KB Output is correct
3 Correct 0 ms 900 KB Output is correct
4 Correct 4 ms 1444 KB Output is correct
5 Correct 4 ms 1348 KB Output is correct
6 Correct 4 ms 1316 KB Output is correct
7 Correct 4 ms 1456 KB Output is correct
8 Correct 4 ms 1444 KB Output is correct
9 Correct 22 ms 4096 KB Output is correct
10 Correct 23 ms 4084 KB Output is correct
11 Correct 22 ms 4040 KB Output is correct
12 Correct 2 ms 900 KB Output is correct
13 Correct 1 ms 1004 KB Output is correct
14 Correct 1 ms 1016 KB Output is correct
15 Correct 0 ms 900 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 4452 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 4640 KB Output isn't correct
2 Halted 0 ms 0 KB -