Submission #876826

#	Time	Username	Problem	Language	Result	Execution time	Memory
876826		vjudge1	Ball Machine (BOI13_ballmachine)	C++17	7.54 / 100	179 ms	30404 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

#define TOF_io ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0)
#define file_io freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int) (x).size()

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef unsigned long long int ull;

const long long inf = 2147483647, INF = 1e18;
const int md = 1e9 + 7;
const int lg = 30 + 2;
const int sq = 320;
const int N = 100 * 1000 + 5;
const int MAXN = 1000 * 1000 + 5;

int n;
int q, p;
int root, sz[N], par[lg][N];
int st[N], ind[N];
int seg[N << 2];
pii a[N];
vector<int> edges[N], vec;
set<pii> s;
bool mark[N];

void upd(int id, int s, int e, int l, int r, int x) {
	if (r <= s || e <= l) return;
	if (l <= s && e <= r) {
		seg[id] += x;
		return;
	}
	
	int mid = (s + e) / 2;
	upd(2 * id,     s, mid, l, r, x);
	upd(2 * id + 1, mid, e, l, r, x);
}

int get(int id, int s, int e, int l, int r) {
	if (r <= s || e <= l) return 0;
	if (l <= s && e <= r) return seg[id];
	
	int mid = (s + e) / 2;
	return seg[id] + get(2 * id,  s, mid,   l, r) +
					 get(2 * id + 1, mid, e, l, r);
}

void dfs(int pr, int v) {
	vec.pb(v);
	
	par[0][v] = pr;
	for (int d = 1; d < lg; d ++) par[d][v] = par[d - 1][par[d - 1][v]];
	
	for (int u: edges[v]) if (u != pr) dfs(v, u);
	
	sz[v] = 1;
	for (int u: edges[v]) if (u != pr) sz[v] += sz[u];
}

void solve(int v, int l, int r) {
	ind[v] = r - 1;
	mark[v] = true;
	
	for (int i = 0; i < edges[v].size(); i ++) {
		int u = edges[v][i];
		if (mark[u]) continue;
		
		solve(u, l, l + sz[u]);
		l += sz[u];
	}
}

int main() {
	TOF_io;
	cin >> n >> q;
	for (int i = 0, pr; i < n; i ++) {
		cin >> pr, pr --;
		
		if (pr < 0) {
			root = i;
			continue;
		}
		
		edges[i].pb(pr), edges[pr].pb(i);
	}
	
	for (int i = 0; i < n; i ++) sort(all(edges[i]));
	
	dfs(0, 0);
	for (int i = 0; i < n; i ++) st[vec[i]] = i;
	
	solve(root, 0, n);
	for (int i = 0; i < n; i ++) a[i].F = ind[i], a[i].S = i;
	sort(a, a + n);
	
	for (int i = 0, t, k; i < q; i ++) {
		cin >> t >> k, t --;
		
		if (t) {
			k --;
			int cnt = get(1, 0, n, st[k], st[k] + 1);
			cnt --;
			
			for (int d = 0; d < lg; d ++) if ((cnt >> d) & 1)
				k = par[d][k];
			
			s.insert({ind[k], k});
			upd(1, 0, n, st[k], st[k] + sz[k], -1);
			cout << cnt << '\n';
		}
		
		else {
			int res = -1;
			while (k && s.size()) {
				auto cur = s.begin();
				
				int v = (*cur).S;
				upd(1, 0, n, st[v], st[v] + sz[v], 1);
				
				s.erase(cur);
				res = v, k --;
			}
			
			while (k --) {
				int v = a[p].S;
				upd(1, 0, n, st[v], st[v] + sz[v], 1);

				res = v;
				p ++;
			}
			
			cout << res + 1 << '\n';
		}
	}
	
	return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'void solve(int, int, int)':
ballmachine.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for (int i = 0; i < edges[v].size(); i ++) {
      |                  ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 25
• Subtask 2: 6.428571428571429 / 30
• Subtask 3: 0 / 40
• Subtask 4: 1.1111111111111112 / 5