oj.uz

Submission #418012

# Submission time Handle Problem Language Result Execution time Memory
418012 2021-06-04T21:12:01 Z Blagojce Ball Machine (BOI13_ballmachine) C++11
0 / 100
 1000 ms 30652 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 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];
		}
	}

	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{
		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 < mxn){
		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 < mxn){
		bit2[k] += v;
		k += k&-k;
	}
}
int sum(int k){
	int ret = 0;
	while(k > 0){
		ret += bit2[k];
		k -= k&-k;
	}
	return ret;
}



void solve(){
	cin >> n >> q;
	fr(i, 0, n){
		int x;
		cin >> x;
		if(x == 0) continue;
		g[x-1].pb(i);
	}
	
	dfs(0, 0);
	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(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
}

Compilation message

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

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 2764 KB Time limit exceeded
2 Execution timed out 1082 ms 5056 KB Time limit exceeded
3 Execution timed out 1074 ms 5160 KB Time limit exceeded
4 Execution timed out 1089 ms 2636 KB Time limit exceeded
5 Execution timed out 1086 ms 2764 KB Time limit exceeded
6 Execution timed out 1090 ms 2764 KB Time limit exceeded
7 Execution timed out 1095 ms 2764 KB Time limit exceeded
8 Execution timed out 1088 ms 2764 KB Time limit exceeded
9 Execution timed out 1096 ms 2892 KB Time limit exceeded
10 Execution timed out 1096 ms 3396 KB Time limit exceeded
11 Execution timed out 1081 ms 5356 KB Time limit exceeded
12 Execution timed out 1094 ms 5164 KB Time limit exceeded
13 Execution timed out 1040 ms 5056 KB Time limit exceeded

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1061 ms 8232 KB Time limit exceeded
2 Execution timed out 1076 ms 25156 KB Time limit exceeded
3 Execution timed out 1091 ms 5828 KB Time limit exceeded
4 Execution timed out 1078 ms 4292 KB Time limit exceeded
5 Execution timed out 1086 ms 4040 KB Time limit exceeded
6 Execution timed out 1098 ms 4000 KB Time limit exceeded
7 Execution timed out 1091 ms 3908 KB Time limit exceeded
8 Execution timed out 1085 ms 8280 KB Time limit exceeded
9 Execution timed out 1091 ms 28096 KB Time limit exceeded
10 Execution timed out 1056 ms 25156 KB Time limit exceeded
11 Execution timed out 1084 ms 6336 KB Time limit exceeded
12 Execution timed out 1091 ms 6328 KB Time limit exceeded
13 Execution timed out 1096 ms 24004 KB Time limit exceeded
14 Execution timed out 1085 ms 5820 KB Time limit exceeded

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 15024 KB Time limit exceeded
2 Execution timed out 1087 ms 25028 KB Time limit exceeded
3 Execution timed out 1092 ms 22080 KB Time limit exceeded
4 Execution timed out 1074 ms 5984 KB Time limit exceeded
5 Execution timed out 1077 ms 5696 KB Time limit exceeded
6 Execution timed out 1081 ms 5696 KB Time limit exceeded
7 Execution timed out 1079 ms 20672 KB Time limit exceeded
8 Execution timed out 1071 ms 22080 KB Time limit exceeded
9 Execution timed out 1078 ms 6784 KB Time limit exceeded
10 Execution timed out 1082 ms 6296 KB Time limit exceeded
11 Execution timed out 1087 ms 24168 KB Time limit exceeded
12 Execution timed out 1087 ms 24900 KB Time limit exceeded
13 Execution timed out 1083 ms 26192 KB Time limit exceeded
14 Execution timed out 1083 ms 5896 KB Time limit exceeded

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 6744 KB Time limit exceeded
2 Execution timed out 1083 ms 25504 KB Time limit exceeded
3 Execution timed out 1092 ms 30620 KB Time limit exceeded
4 Execution timed out 1061 ms 6752 KB Time limit exceeded
5 Execution timed out 1034 ms 6376 KB Time limit exceeded
6 Execution timed out 1089 ms 26780 KB Time limit exceeded
7 Execution timed out 1081 ms 25532 KB Time limit exceeded
8 Execution timed out 1092 ms 30652 KB Time limit exceeded
9 Execution timed out 1083 ms 5820 KB Time limit exceeded