oj.uz

Submission #968920

# Submission time Handle Problem Language Result Execution time Memory
968920 2024-04-24T09:41:36 Z NintsiChkhaidze Ball Machine (BOI13_ballmachine) C++17
100 / 100
 440 ms 39108 KB 
#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define left (h*2),l,(l + r)/2
#define right (h*2+1),(l+r)/2 + 1,r
#define pii pair <int,int>
using namespace std;

const int N = 1e5 + 5;

vector <int> v[N];
int ord[N],mn[N],sub[N];
int pr[N],fix[N],d[25][N],t[4*N],id[N];
int lz[4*N],dep[N];

void predfs(int x,int par){
	mn[x] = x;
	dep[x] = dep[par] + 1;
	d[0][x] = par;
	sub[x] = 1;
	for (int to: v[x]){
		if (to == par) continue;
		predfs(to,x);
		mn[x] = min(mn[x],mn[to]);
		sub[x] += sub[to];
	}
}

void dfs(int x,int par,int l,int r){
	
	vector <pii> vec;
	for (int to: v[x]){
		if (to != par) vec.pb({mn[to],to});
	}
	sort(vec.begin(),vec.end());

	int L = l;
	for (auto [p,to]: vec){
		dfs(to,x,L,L + sub[to] - 1);
		L += sub[to];
	}
	ord[r] = x;
}

void build(int h,int l,int r){
	lz[h] = -1;
	if (l == r){
		t[h] = 0;
		return;
	}
	build(left);
	build(right);
	t[h] = t[h*2] + t[h*2 + 1];
}

void push(int h,int l,int r){
	if (lz[h] == -1) return;
	lz[h*2] = lz[h*2+ 1] = lz[h];

	t[h*2] = ((r + l)/2 - l + 1)*lz[h];
	t[h*2 + 1] = (r - (r + l)/2)*lz[h];
	lz[h] = -1;
}

int findk(int h,int l,int r,int k){
	if (l == r) return l;
	push(h,l,r);
	int lft = (l + r)/2 - l + 1 - t[h*2];
	if (lft >= k) return findk(left,k);
	return findk(right,k - lft);
}

void upd(int h,int l,int r,int L,int R,int vl){
	if (r < L || R < l) return;
	if (L <= l && r <= R){
		t[h] = vl * (r - l + 1);
		lz[h] = vl;
		return;
	}

	push(h,l,r);
	upd(left,L,R,vl);
	upd(right,L,R,vl);
	t[h] = t[h*2] + t[h*2 + 1];
}

int get(int h,int l,int r,int idx){
	if (l == r) return t[h];
	push(h,l,r);
	if (idx > (l + r)/2) return get(right,idx);
	return get(left,idx);
}

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

	int n,q,root;
	cin>>n>>q;

	for (int i = 1; i <= n; i++){
		int p;
		cin>>p;
		if (!p) root=i;
		else {
			pr[i] = p;
			v[p].pb(i);
			v[i].pb(p);
		}
	}

	predfs(root,root);
	dfs(root,root,1,n);

	for (int i = 1; i <= n; i++)
		id[ord[i]] = i;
	build(1,1,n);
	for (int i = 1; i <= 18; i++)
		for (int j = 1; j <= n; j++)
			d[i][j] = d[i - 1][d[i - 1][j]];
		
	while (q--){
		int tp,x;
		cin>>tp>>x;

		if (tp == 1){
			int len = findk(1,1,n,x); // me-x nuli vipovot
			upd(1,1,n,1,len,1);
			cout<<ord[len]<<endl;
			continue;
		}

		int y = x,len = 0;
		for (int i = 18; i >= 0; i--){
			if (dep[y] > (1<<i) && get(1,1,n,id[d[i][y]])) { 
				len += (1<<i);
				y = d[i][y];
			}
		}

		upd(1,1,n,id[y],id[y],0);
		cout<<len<<endl;
	}	
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:114:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  114 |  dfs(root,root,1,n);
      |  ~~~^~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18268 KB Output is correct
2 Correct 205 ms 21660 KB Output is correct
3 Correct 172 ms 21636 KB Output is correct
4 Correct 3 ms 18268 KB Output is correct
5 Correct 3 ms 18268 KB Output is correct
6 Correct 4 ms 18268 KB Output is correct
7 Correct 6 ms 18524 KB Output is correct
8 Correct 6 ms 18268 KB Output is correct
9 Correct 21 ms 18268 KB Output is correct
10 Correct 42 ms 19112 KB Output is correct
11 Correct 216 ms 20620 KB Output is correct
12 Correct 167 ms 22224 KB Output is correct
13 Correct 193 ms 21812 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 22352 KB Output is correct
2 Correct 385 ms 31284 KB Output is correct
3 Correct 169 ms 23080 KB Output is correct
4 Correct 186 ms 22608 KB Output is correct
5 Correct 229 ms 22496 KB Output is correct
6 Correct 232 ms 22500 KB Output is correct
7 Correct 220 ms 21596 KB Output is correct
8 Correct 139 ms 22356 KB Output is correct
9 Correct 328 ms 30420 KB Output is correct
10 Correct 374 ms 31040 KB Output is correct
11 Correct 340 ms 31060 KB Output is correct
12 Correct 346 ms 26712 KB Output is correct
13 Correct 214 ms 36480 KB Output is correct
14 Correct 171 ms 23364 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 23380 KB Output is correct
2 Correct 362 ms 27176 KB Output is correct
3 Correct 223 ms 33872 KB Output is correct
4 Correct 188 ms 28240 KB Output is correct
5 Correct 225 ms 28240 KB Output is correct
6 Correct 234 ms 28596 KB Output is correct
7 Correct 207 ms 25216 KB Output is correct
8 Correct 241 ms 34140 KB Output is correct
9 Correct 290 ms 31060 KB Output is correct
10 Correct 418 ms 31572 KB Output is correct
11 Correct 436 ms 30696 KB Output is correct
12 Correct 417 ms 27276 KB Output is correct
13 Correct 360 ms 38564 KB Output is correct
14 Correct 202 ms 22804 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 30716 KB Output is correct
2 Correct 400 ms 27172 KB Output is correct
3 Correct 227 ms 38740 KB Output is correct
4 Correct 334 ms 30804 KB Output is correct
5 Correct 440 ms 31128 KB Output is correct
6 Correct 346 ms 31208 KB Output is correct
7 Correct 361 ms 27260 KB Output is correct
8 Correct 228 ms 39108 KB Output is correct
9 Correct 191 ms 23060 KB Output is correct