# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
333828 | 2020-12-07T20:55:26 Z | CaroLinda | Ball Machine (BOI13_ballmachine) | C++14 | 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
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 |
# | 결과 | 실행 시간 | 메모리 | 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 |