oj.uz

Submission #979216

# Submission time Handle Problem Language Result Execution time Memory
979216 2024-05-10T11:53:00 Z batsukh2006 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 171 ms 46836 KB 
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<map>
#include<string>
#include<algorithm>
#include<vector>
#include<string.h>
#include<utility>
#include<set>
#include<cmath>
#include<queue>
#include<deque>
#include<functional>
#include<stack>
#include<limits.h>
#include<iomanip>
#include<unordered_map> 
#include<numeric>
#include<tuple>
using namespace std;
 
#define MOD 1000000009
#define int long long
#define ff first
#define ss second
#define endl '\n'
typedef pair<int,int> pp;
int order=0;
const int mxN=1e5+1;
vector<bool> e(mxN);
vector<vector<int> > p(mxN,vector<int>(20));
vector<int> lvl(mxN),o(mxN),v[mxN],dp(mxN,1e9);
void pre(int a, int d){
	lvl[a]=d;
	for(auto node: v[a]){
		pre(node,d+1);
		dp[a]=min(dp[a],dp[node]);
	}
	dp[a]=min(dp[a],a);
}
void dfs(int a){
	vector<pp> t;
	for(auto node: v[a]){
		t.push_back({dp[node],node});
	}
	sort(t.begin(),t.end());
	for(auto node: t) dfs(node.ss);
	o[a]=++order;
}
int find(int a){
    for(int i=19; i>=0; i--){
        if(e[p[a][i]]) a=p[a][i];
    }
    return a;
}
signed main(){
    // freopen("248.in", "r", stdin);
    // freopen("248.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
	int n,m; cin>>n>>m;
	for(int i=1; i<=n; i++){
		cin>>p[i][0];
		v[p[i][0]].push_back(i);
	}
	pre(0,0);
	dfs(0);
	for(int i=1; i<20; i++){
        for(int j=1; j<=n; j++){
            p[j][i]=p[p[j][i-1]][i-1];
        }
    }
    priority_queue<pp,vector<pp>,greater<pp> > q;
    for(int i=1; i<=n; i++) q.push({o[i],i});
	while(m--){
		int t,x; cin>>t>>x;
		if(t==1){
			int r;
			while(x--){
				r=q.top().ss;
				e[r]=true;
				q.pop();
			}
			cout<<r<<endl;
		}else{
			int c=find(x);
			e[c]=false;
			q.push({o[c],c});
			cout<<lvl[x]-lvl[c]<<endl;
		}
	}
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24668 KB Output is correct
2 Correct 87 ms 28108 KB Output is correct
3 Correct 56 ms 28132 KB Output is correct
4 Correct 12 ms 24668 KB Output is correct
5 Correct 12 ms 24664 KB Output is correct
6 Correct 12 ms 24668 KB Output is correct
7 Correct 14 ms 24576 KB Output is correct
8 Correct 13 ms 24668 KB Output is correct
9 Correct 17 ms 24924 KB Output is correct
10 Correct 26 ms 25560 KB Output is correct
11 Correct 85 ms 28112 KB Output is correct
12 Correct 56 ms 28112 KB Output is correct
13 Correct 75 ms 28112 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 29124 KB Output is correct
2 Correct 127 ms 38184 KB Output is correct
3 Correct 76 ms 30016 KB Output is correct
4 Correct 55 ms 29008 KB Output is correct
5 Correct 69 ms 29076 KB Output is correct
6 Correct 55 ms 29048 KB Output is correct
7 Correct 57 ms 27804 KB Output is correct
8 Correct 38 ms 29192 KB Output is correct
9 Correct 117 ms 38220 KB Output is correct
10 Correct 128 ms 38332 KB Output is correct
11 Correct 130 ms 38384 KB Output is correct
12 Correct 116 ms 33868 KB Output is correct
13 Correct 84 ms 44116 KB Output is correct
14 Correct 70 ms 30044 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 31436 KB Output is correct
2 Correct 135 ms 34128 KB Output is correct
3 Correct 121 ms 42088 KB Output is correct
4 Correct 106 ms 35672 KB Output is correct
5 Correct 91 ms 35724 KB Output is correct
6 Correct 89 ms 35668 KB Output is correct
7 Correct 94 ms 32336 KB Output is correct
8 Correct 106 ms 42068 KB Output is correct
9 Correct 135 ms 38224 KB Output is correct
10 Correct 140 ms 38364 KB Output is correct
11 Correct 132 ms 38552 KB Output is correct
12 Correct 146 ms 34128 KB Output is correct
13 Correct 171 ms 46836 KB Output is correct
14 Correct 119 ms 30044 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 38368 KB Output is correct
2 Correct 137 ms 34128 KB Output is correct
3 Correct 98 ms 46648 KB Output is correct
4 Correct 137 ms 38224 KB Output is correct
5 Correct 144 ms 38560 KB Output is correct
6 Correct 106 ms 38292 KB Output is correct
7 Correct 141 ms 34128 KB Output is correct
8 Correct 98 ms 46420 KB Output is correct
9 Correct 91 ms 30104 KB Output is correct