oj.uz

Submission #313730

# Submission time Handle Problem Language Result Execution time Memory
313730 2020-10-16T20:18:36 Z CaroLinda Amusement Park (JOI17_amusement_park) C++14
10 / 100
 36 ms 5024 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) ;

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

	for(int i = 0 ; i < N ; i++ ) sort(all(graph[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 = 200 ;

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1008 KB Output is correct
2 Correct 1 ms 900 KB Output is correct
3 Correct 2 ms 912 KB Output is correct
4 Correct 1 ms 776 KB Output is correct
5 Correct 1 ms 1016 KB Output is correct
6 Incorrect 2 ms 904 KB Wrong Answer [7]
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 4580 KB Output is correct
2 Correct 34 ms 4644 KB Output is correct
3 Correct 33 ms 5024 KB Output is correct
4 Correct 19 ms 3636 KB Output is correct
5 Correct 19 ms 3808 KB Output is correct
6 Correct 19 ms 3888 KB Output is correct
7 Correct 20 ms 3644 KB Output is correct
8 Correct 19 ms 3852 KB Output is correct
9 Correct 19 ms 3772 KB Output is correct
10 Correct 19 ms 3520 KB Output is correct
11 Correct 20 ms 3608 KB Output is correct
12 Correct 17 ms 3328 KB Output is correct
13 Correct 17 ms 3396 KB Output is correct
14 Correct 20 ms 3288 KB Output is correct
15 Correct 19 ms 3508 KB Output is correct
16 Correct 19 ms 3260 KB Output is correct
17 Correct 20 ms 3632 KB Output is correct
18 Correct 19 ms 3632 KB Output is correct
19 Correct 19 ms 3768 KB Output is correct
20 Incorrect 16 ms 3768 KB Wrong Answer [7]
21 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 900 KB Output is correct
2 Correct 1 ms 904 KB Output is correct
3 Correct 1 ms 776 KB Output is correct
4 Correct 4 ms 1348 KB Output is correct
5 Correct 3 ms 1728 KB Output is correct
6 Correct 4 ms 1348 KB Output is correct
7 Correct 4 ms 1568 KB Output is correct
8 Correct 4 ms 1476 KB Output is correct
9 Correct 18 ms 4280 KB Output is correct
10 Correct 16 ms 4280 KB Output is correct
11 Correct 19 ms 4344 KB Output is correct
12 Correct 1 ms 1020 KB Output is correct
13 Correct 2 ms 776 KB Output is correct
14 Correct 1 ms 1020 KB Output is correct
15 Correct 1 ms 1020 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Partially correct 32 ms 4452 KB Partially correct
2 Partially correct 36 ms 4656 KB Partially correct
3 Partially correct 32 ms 4908 KB Partially correct
4 Partially correct 19 ms 3496 KB Partially correct
5 Partially correct 25 ms 4212 KB Partially correct
6 Partially correct 19 ms 3844 KB Partially correct
7 Partially correct 19 ms 3844 KB Partially correct
8 Partially correct 19 ms 3672 KB Partially correct
9 Partially correct 22 ms 3900 KB Partially correct
10 Partially correct 18 ms 3600 KB Partially correct
11 Partially correct 20 ms 3392 KB Partially correct
12 Partially correct 17 ms 3340 KB Partially correct
13 Partially correct 18 ms 3236 KB Partially correct
14 Partially correct 19 ms 3376 KB Partially correct
15 Partially correct 19 ms 3644 KB Partially correct
16 Partially correct 19 ms 3516 KB Partially correct
17 Partially correct 19 ms 3388 KB Partially correct
18 Partially correct 19 ms 3420 KB Partially correct
19 Partially correct 19 ms 3516 KB Partially correct
20 Incorrect 17 ms 4044 KB Wrong Answer [7]
21 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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