oj.uz

답안 #418024

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
418024 2021-06-04T21:41:38 Z Blagojce Ball Machine (BOI13_ballmachine) C++11
44.0842 / 100
 667 ms 33852 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];

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];
				
				update2(eul[node], +1);
				update2(eul[node]+sub[node], -1);
				
				o = p;
			}
			cout<<v[o-1]+1<<endl;
		}
		else{
			--x;
			int D = sum(eul[x]);
			
			for(int i = 19; i >= 0; i--){
				if(D - 1 - (1<<i) >= 0){
					x = sparse[x][i];
				}
			}
			
			cout<<D-1<<endl;
			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:203:13: warning: 'o' may be used uninitialized in this function [-Wmaybe-uninitialized]
  203 |    cout<<v[o-1]+1<<endl;
      |            ~^~

Subtask #1
3.84615384615 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2764 KB Output isn't correct
2 Incorrect 412 ms 16888 KB Output isn't correct
3 Correct 377 ms 16564 KB Output is correct
4 Incorrect 2 ms 2636 KB Output isn't correct
5 Incorrect 2 ms 2764 KB Output isn't correct
6 Incorrect 5 ms 2892 KB Output isn't correct
7 Incorrect 5 ms 2892 KB Output isn't correct
8 Incorrect 6 ms 2892 KB Output isn't correct
9 Incorrect 25 ms 3612 KB Output isn't correct
10 Incorrect 81 ms 6252 KB Output isn't correct
11 Incorrect 396 ms 16820 KB Output isn't correct
12 Correct 393 ms 16580 KB Output is correct
13 Incorrect 393 ms 16448 KB Output isn't correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 198 ms 8484 KB Output is correct
2 Correct 642 ms 28168 KB Output is correct
3 Correct 485 ms 23224 KB Output is correct
4 Correct 245 ms 10820 KB Output is correct
5 Correct 252 ms 10492 KB Output is correct
6 Correct 245 ms 10348 KB Output is correct
7 Correct 243 ms 9384 KB Output is correct
8 Correct 184 ms 8516 KB Output is correct
9 Correct 561 ms 28504 KB Output is correct
10 Correct 624 ms 28096 KB Output is correct
11 Correct 630 ms 27716 KB Output is correct
12 Correct 618 ms 25672 KB Output is correct
13 Correct 519 ms 29504 KB Output is correct
14 Correct 485 ms 23312 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 264 ms 15960 KB Output isn't correct
2 Incorrect 659 ms 26716 KB Output isn't correct
3 Correct 457 ms 27536 KB Output is correct
4 Incorrect 423 ms 23740 KB Output isn't correct
5 Incorrect 445 ms 23488 KB Output isn't correct
6 Incorrect 486 ms 23492 KB Output isn't correct
7 Incorrect 450 ms 21908 KB Output isn't correct
8 Correct 452 ms 27712 KB Output is correct
9 Incorrect 611 ms 29164 KB Output isn't correct
10 Incorrect 663 ms 28896 KB Output isn't correct
11 Incorrect 663 ms 28732 KB Output isn't correct
12 Incorrect 659 ms 26944 KB Output isn't correct
13 Correct 641 ms 33852 KB Output is correct
14 Incorrect 494 ms 24252 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 641 ms 28892 KB Output isn't correct
2 Incorrect 667 ms 26904 KB Output isn't correct
3 Correct 574 ms 32916 KB Output is correct
4 Incorrect 631 ms 29156 KB Output isn't correct
5 Incorrect 666 ms 28676 KB Output isn't correct
6 Incorrect 652 ms 27852 KB Output isn't correct
7 Incorrect 642 ms 26684 KB Output isn't correct
8 Correct 571 ms 32908 KB Output is correct
9 Correct 499 ms 23284 KB Output is correct