oj.uz

Submission #333827

# Submission time Handle Problem Language Result Execution time Memory
333827 2020-12-07T20:47:19 Z CaroLinda Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 1000 ms 30572 KB 
#include <bits/stdc++.h>
 
#define debug printf
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )
#define ll long long

const int MAXN = 1e5+10 ;
const int LOG = 20 ;

using namespace std ;

int N , Q , root ;
int dp[LOG][MAXN] ;
int tout[MAXN] , lvl[MAXN] ;
bool hasBall[MAXN] ;
vector<int> adj[MAXN] ;
set<pair<int,int > > available;

int currTime ;
void dfs(int x)
{

	for(int i = 1 ; i < LOG ; i++ )
		if( dp[i-1][x] != -1 )
			dp[i][x] = dp[i-1][ dp[i-1][x] ] ;
	
	tout[x] = ++currTime ;	      	

	sort(all(adj[x] ) ) ;
	for(auto e : adj[x] )
	{
		dp[0][e] = x ;
		lvl[e] = lvl[x] + 1 ;
		dfs(e) ;
		tout[x] = ++currTime ;
	}

	available.insert( make_pair(tout[x],x) ) ;

}

int main()
{

	scanf("%d %d", &N, &Q ) ;
	for(int i = 1 , parent ; i <= N ; i++ )
	{
		scanf("%d", &parent ) ;

		if( parent == 0 ) root = i ;
		else adj[ parent ].push_back(i) ;
	}

	for(int i = 0 ; i < LOG ; i++ )
		for(int j = 1 ; j <= N ; j++ ) dp[i][j] = -1 ;

	dfs(root) ;

	for(int trash = 0, type , k ; trash < Q ; trash++ )
	{
		scanf("%d %d", &type, &k ) ;

		if(type == 1 )
		{
			int resp = -1 ;
			while( k )
			{
				resp = available.begin()->second ;
				hasBall[resp] = true ;
				available.erase( available.begin() ) ;
				k-- ;
			}

			printf("%d\n", resp ) ;

		}
		else 
		{
			int x = k ;

			for(int i = LOG-1 ; i >= 0 ; i-- )
			{
				if( dp[i][x] == -1 ) continue ;
				if( hasBall[ dp[i][x] ] ) x = dp[i][x] ;		
			}

			available.insert( make_pair( tout[x], x ) ) ;
			hasBall[x] = false ; 
			printf("%d\n", lvl[k]-lvl[x] ) ;
		}

	}

}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |  scanf("%d %d", &N, &Q ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~
ballmachine.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |   scanf("%d", &parent ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~
ballmachine.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |   scanf("%d %d", &type, &k ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2796 KB Output isn't correct
2 Execution timed out 1093 ms 13804 KB Time limit exceeded
3 Incorrect 99 ms 14060 KB Output isn't correct
4 Execution timed out 1089 ms 2796 KB Time limit exceeded
5 Incorrect 3 ms 2796 KB Output isn't correct
6 Incorrect 3 ms 2924 KB Output isn't correct
7 Execution timed out 1089 ms 2924 KB Time limit exceeded
8 Execution timed out 1050 ms 2924 KB Time limit exceeded
9 Incorrect 10 ms 3436 KB Output isn't correct
10 Execution timed out 1093 ms 5484 KB Time limit exceeded
11 Incorrect 203 ms 13932 KB Output isn't correct
12 Incorrect 98 ms 13932 KB Output isn't correct
13 Incorrect 159 ms 13932 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 8300 KB Output is correct
2 Incorrect 367 ms 24556 KB Output isn't correct
3 Incorrect 119 ms 18792 KB Output isn't correct
4 Execution timed out 1093 ms 9600 KB Time limit exceeded
5 Execution timed out 1038 ms 9324 KB Time limit exceeded
6 Incorrect 102 ms 9984 KB Output isn't correct
7 Incorrect 117 ms 8684 KB Output isn't correct
8 Correct 47 ms 8300 KB Output is correct
9 Incorrect 315 ms 24684 KB Output isn't correct
10 Incorrect 370 ms 24428 KB Output isn't correct
11 Incorrect 276 ms 24428 KB Output isn't correct
12 Incorrect 354 ms 21740 KB Output isn't correct
13 Correct 156 ms 27116 KB Output is correct
14 Incorrect 120 ms 18792 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 120 ms 13884 KB Output isn't correct
2 Incorrect 395 ms 22252 KB Output isn't correct
3 Correct 205 ms 24684 KB Output is correct
4 Incorrect 193 ms 20332 KB Output isn't correct
5 Incorrect 240 ms 19948 KB Output isn't correct
6 Incorrect 239 ms 20204 KB Output isn't correct
7 Incorrect 243 ms 18156 KB Output isn't correct
8 Correct 214 ms 24812 KB Output is correct
9 Incorrect 315 ms 24940 KB Output isn't correct
10 Incorrect 387 ms 24428 KB Output isn't correct
11 Incorrect 388 ms 24428 KB Output isn't correct
12 Incorrect 380 ms 22124 KB Output isn't correct
13 Correct 323 ms 30572 KB Output is correct
14 Incorrect 235 ms 19048 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 312 ms 24952 KB Output isn't correct
2 Incorrect 369 ms 22124 KB Output isn't correct
3 Correct 170 ms 30060 KB Output is correct
4 Incorrect 300 ms 24812 KB Output isn't correct
5 Incorrect 366 ms 24428 KB Output isn't correct
6 Incorrect 268 ms 24428 KB Output isn't correct
7 Incorrect 366 ms 22124 KB Output isn't correct
8 Correct 173 ms 30060 KB Output is correct
9 Incorrect 118 ms 18664 KB Output isn't correct