oj.uz

답안 #333828

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
333828 2020-12-07T20:55:26 Z CaroLinda Ball Machine (BOI13_ballmachine) C++14
100 / 100
 381 ms 28236 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] , sub[MAXN] ;
bool hasBall[MAXN] ;
vector<int> adj[MAXN] ;
set<pair<int,int > > available;

int currTime ;
void dfs1(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] ] ;

	sub[x] = x ;	      	

	for(auto e : adj[x] )
	{
		dp[0][e] = x ;
		lvl[e] = lvl[x] + 1 ;
		dfs1(e) ;
		sub[x] = min(sub[x] , sub[e] ) ;
	}

}

void dfs2(int x)
{

	sort(all(adj[x] ), [&](int i, int j ) { return sub[i] < sub[j] ; } ) ;

	tout[x] = ++currTime ;

	for(auto e : adj[x] )
	{
		dfs2(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 ;

	dfs1(root) ;
	dfs2(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:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |  scanf("%d %d", &N, &Q ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~
ballmachine.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |   scanf("%d", &parent ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~
ballmachine.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |   scanf("%d %d", &type, &k ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2796 KB Output is correct
2 Correct 186 ms 13048 KB Output is correct
3 Correct 98 ms 13420 KB Output is correct
4 Correct 2 ms 2796 KB Output is correct
5 Correct 2 ms 2796 KB Output is correct
6 Correct 3 ms 2924 KB Output is correct
7 Correct 3 ms 2924 KB Output is correct
8 Correct 3 ms 2924 KB Output is correct
9 Correct 10 ms 3436 KB Output is correct
10 Correct 27 ms 5484 KB Output is correct
11 Correct 192 ms 13168 KB Output is correct
12 Correct 97 ms 13164 KB Output is correct
13 Correct 142 ms 13036 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 7552 KB Output is correct
2 Correct 375 ms 22636 KB Output is correct
3 Correct 121 ms 17896 KB Output is correct
4 Correct 98 ms 9068 KB Output is correct
5 Correct 121 ms 9324 KB Output is correct
6 Correct 101 ms 8812 KB Output is correct
7 Correct 102 ms 7788 KB Output is correct
8 Correct 47 ms 7532 KB Output is correct
9 Correct 318 ms 22892 KB Output is correct
10 Correct 377 ms 22508 KB Output is correct
11 Correct 272 ms 22508 KB Output is correct
12 Correct 346 ms 20332 KB Output is correct
13 Correct 157 ms 24940 KB Output is correct
14 Correct 125 ms 18024 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 110 ms 13036 KB Output is correct
2 Correct 355 ms 20716 KB Output is correct
3 Correct 216 ms 23020 KB Output is correct
4 Correct 192 ms 19180 KB Output is correct
5 Correct 231 ms 18668 KB Output is correct
6 Correct 234 ms 18668 KB Output is correct
7 Correct 225 ms 17132 KB Output is correct
8 Correct 200 ms 22892 KB Output is correct
9 Correct 303 ms 23148 KB Output is correct
10 Correct 381 ms 22764 KB Output is correct
11 Correct 375 ms 22892 KB Output is correct
12 Correct 378 ms 20716 KB Output is correct
13 Correct 332 ms 28236 KB Output is correct
14 Correct 237 ms 18024 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 302 ms 23276 KB Output is correct
2 Correct 367 ms 20716 KB Output is correct
3 Correct 176 ms 27884 KB Output is correct
4 Correct 302 ms 23276 KB Output is correct
5 Correct 363 ms 22764 KB Output is correct
6 Correct 267 ms 22636 KB Output is correct
7 Correct 363 ms 20844 KB Output is correct
8 Correct 176 ms 27756 KB Output is correct
9 Correct 121 ms 17896 KB Output is correct