oj.uz

답안 #418026

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
418026 2021-06-04T21:55:11 Z Blagojce Ball Machine (BOI13_ballmachine) C++11
100 / 100
 665 ms 33932 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
  
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const ll inf = 1e18;
const int i_inf = 1e9;
const ll mod = 1e9+7;
 
mt19937 _rand(time(NULL));
const int mxn = 1e5+5;
 
 
vector<int> g[mxn];
 
int n, q;
int dep[mxn];

int sparse[mxn][20];
int mi[mxn][20];

int sub[mxn];
int msub[mxn];

int t_p = 1;
int eul[mxn];
int ieul[mxn];


void dfs(int u, int p){
	
	
	ieul[t_p] = u;
	eul[u] = t_p++;
	
	sparse[u][0] = p;
	fr(i, 1, 20) sparse[u][i] = sparse[sparse[u][i-1]][i-1];

	mi[u][0] = min(u, p);
	fr(i, 1, 20){
		mi[u][i] = min(mi[u][i-1], mi[sparse[u][i-1]][i-1]);
	}
	
	msub[u] = u;
	sub[u] = 1;
	for(auto e : g[u]){
		dep[e] = dep[u]+1;
		dfs(e, u);
		msub[u] = min(msub[u], msub[e]);
		sub[u] += sub[e];
	}
}
int A, B;
int lca(int a, int b){
	int d = min(dep[a], dep[b]);
	
	for(int i = 19; i >= 0; i --){
		if(dep[a] - (1<<i) >= d){
			a = sparse[a][i];
		}
		if(dep[b] - (1<<i) >= d){
			b = sparse[b][i];
		}
	}

	
	if(a == b) return a;
	for(int i = 19; i >= 0; i --){
		if(sparse[a][i] != sparse[b][i]){
			a = sparse[a][i];
			b = sparse[b][i];
		}
	}
	A = a;
	B = b;
	return sparse[a][0];
}

int path(int u, int p){
	int ret = n;
	
	
	for(int i = 19; i >= 0; i--){
		if(dep[u] - (1<<i) > dep[p]){
			ret = min(ret, mi[u][i]);
			u = sparse[u][i];
		}
	}
	
	
	return ret;
}

bool cmp(int a, int b){
	int c = lca(a, b);
	
	if(b == c) return true;
	else if(a == c) return false;
	else{
		return msub[A] < msub[B];
		/*int m1 = min(path(a, c), msub[a]);
		int m2 = min(path(b, c), msub[b]);
		return m1 < m2;*/
	}

}

vector<int> v;

int bit[mxn];
void update(int k, int v){
	while(k <= n){
		bit[k] += v;
		k += k&-k;
	}
}

int findpos(){
	int k = 0;
	int sum = 0;
	
	for(int i = 19; i >= 0; i --){
		if(k + (1<<i) <= n && sum + bit[k+(1<<i)] == k+(1<<i)){
			k += (1<<i);
			sum += bit[k];
		}
	}
	return k + 1;
}
int pos[mxn];

int bit2[mxn];


void update2(int k, int v){
	while(k <= n){
		bit2[k] += v;
		k += k&-k;
	}
}
int sum(int k){
	int ret = 0;
	while(k > 0){
		ret += bit2[k];
		k -= k&-k;
	}
	return ret;
}


	int link[mxn];

bool active[mxn];
void solve(){
	cin >> n >> q;
	int r = 0;
	
	fr(i, 0, n){
		int x;
		cin >> x;
		if(x == 0){
			r = i;
			continue;
		}
		link[i] = x-1;
		g[x-1].pb(i);
	}
	
	dfs(r, r);
	fr(i, 0, n) v.pb(i);
	sort(all(v), cmp);
	fr(i, 0, n) pos[v[i]] = i+1;
	
	

	
	fr(i, 0, q){
		char t;
		int x;
		cin >> t >> x;
		if(t == '1'){
			
			int o;
			fr(i, 0, x){
				int p = findpos();
				
				update(p, +1);
				
				int node = v[p-1];
				active[node] = true;
				
				
				update2(eul[node], +1);
				update2(eul[node] + sub[node], -1);
				
				o = p;
			}
			cout<<v[o-1]+1<<endl;
		}
		else{
			--x;
			/*int ans = 0;
			int D = sum(eul[x]);
			while(x != r && active[link[x]]){
				x = link[x];
				++ans;
			}
			cout<<ans<<' '<<D-1<<endl;
			
			
			
			
			
			update(pos[x], -1);
			update2(eul[x], -1);
			update2(eul[x]+sub[x], +1);
			active[x] = false;
			*/
			
			
			
			int D = sum(eul[x]);
			
			cout<<D-1<<endl;
			--D;
			for(int i = 19; i >= 0; i--){
				if(D- (1<<i) >= 0){
					x = sparse[x][i];
					D -= (1<<i);
				}
			}
			
			update(pos[x], -1);
			update2(eul[x], -1);
			update2(eul[x]+sub[x], +1);
		}
		
	}
}
int main(){
	//freopen("ballmachine.g01-1.in", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
}

Compilation message

ballmachine.cpp: In function 'void solve()':
ballmachine.cpp:207:13: warning: 'o' may be used uninitialized in this function [-Wmaybe-uninitialized]
  207 |    cout<<v[o-1]+1<<endl;
      |            ~^~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 416 ms 16860 KB Output is correct
3 Correct 387 ms 16512 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 5 ms 2892 KB Output is correct
7 Correct 6 ms 2892 KB Output is correct
8 Correct 6 ms 2892 KB Output is correct
9 Correct 26 ms 3620 KB Output is correct
10 Correct 83 ms 6168 KB Output is correct
11 Correct 416 ms 16936 KB Output is correct
12 Correct 381 ms 16596 KB Output is correct
13 Correct 419 ms 16500 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 185 ms 8508 KB Output is correct
2 Correct 659 ms 28136 KB Output is correct
3 Correct 477 ms 23444 KB Output is correct
4 Correct 262 ms 10740 KB Output is correct
5 Correct 250 ms 10516 KB Output is correct
6 Correct 252 ms 10584 KB Output is correct
7 Correct 244 ms 9340 KB Output is correct
8 Correct 188 ms 8512 KB Output is correct
9 Correct 573 ms 28700 KB Output is correct
10 Correct 637 ms 28188 KB Output is correct
11 Correct 622 ms 27788 KB Output is correct
12 Correct 621 ms 25656 KB Output is correct
13 Correct 528 ms 29684 KB Output is correct
14 Correct 489 ms 23216 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 261 ms 15944 KB Output is correct
2 Correct 659 ms 26708 KB Output is correct
3 Correct 435 ms 27604 KB Output is correct
4 Correct 416 ms 23612 KB Output is correct
5 Correct 440 ms 23392 KB Output is correct
6 Correct 461 ms 23304 KB Output is correct
7 Correct 459 ms 21860 KB Output is correct
8 Correct 450 ms 27496 KB Output is correct
9 Correct 614 ms 29216 KB Output is correct
10 Correct 649 ms 28760 KB Output is correct
11 Correct 657 ms 28608 KB Output is correct
12 Correct 649 ms 26708 KB Output is correct
13 Correct 629 ms 33932 KB Output is correct
14 Correct 518 ms 24180 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 619 ms 28872 KB Output is correct
2 Correct 634 ms 26428 KB Output is correct
3 Correct 584 ms 32872 KB Output is correct
4 Correct 636 ms 28868 KB Output is correct
5 Correct 665 ms 28604 KB Output is correct
6 Correct 644 ms 27840 KB Output is correct
7 Correct 655 ms 26480 KB Output is correct
8 Correct 583 ms 33028 KB Output is correct
9 Correct 494 ms 23332 KB Output is correct