oj.uz

Submission #313715

# Submission time Handle Problem Language Result Execution time Memory
313715 2020-10-16T19:52:47 Z CaroLinda Amusement Park (JOI17_amusement_park) C++14
0 / 100
 34 ms 5164 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] ) ;
	}

	dfs(0) ;

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

  for(int i = 0 ; i < sz(ordem) ; i++ )
  {
  	if( i-120 >= 0 )
  		freq[ val[ordem[i-120]] ]-- ;

  	if(val[ ordem[i] ] == -1)
  	{
  		val[ordem[i]] = 0 ;

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

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

	dfsPrime(0) ;

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

  for(int i = 0 ; i < sz(ord) ; i++ )
  {
  	if( i-120 >= 0 )
  		freq[ val[ord[i-120]] ]-- ;

  	if(val[ ord[i] ] == -1)
  	{
  		val[ord[i]] = 0 ;

  		for(int j = 0 ; j < 60 ; j++ )
  			if(freq[j] == 0) 
  			{
  				val[ ord[i] ] = j ;
  				break ;
  			}
  	}
  	
  	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 = 120 ;

  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:92:26: warning: 'ptrEn' may be used uninitialized in this function [-Wmaybe-uninitialized]
   92 |   if(ptrBeg == 0 || ptrEn+1 == sz(ord)) break ;
      |                     ~~~~~^~
Ioi.cpp:106:51: warning: 'ptrBeg' may be used uninitialized in this function [-Wmaybe-uninitialized]
  106 |    achei[ val[ ord[ptrBeg-1] ] ] = Move(ord[ptrBeg-1]) ;
      |                                             ~~~~~~^~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4920 KB Output is correct
2 Incorrect 30 ms 4900 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4908 KB Output is correct
2 Incorrect 30 ms 5164 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 4900 KB Output is correct
2 Correct 31 ms 4772 KB Output is correct
3 Incorrect 31 ms 4900 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -