제출 #117119

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
117119		MB81	Ball Machine (BOI13_ballmachine)	C++11	100 / 100	371 ms	26232 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;
typedef long long int64;
typedef pair<int,int> pii;
typedef pair<int64,int> pii32;
typedef pair<int64,int64> pii64;

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

const int maxn = 1e5+10;
const int lg = 18;
const int64 MO = 1e9+7;
const int64 IN = 1e9;

set <pii> s1;
vector <int> g[maxn];
int mn[maxn], fins[maxn], fine[maxn], fen[maxn], par[maxn][lg];
int n, q;

bool cmp (int id1, int id2) {
	return (mn[id1] < mn[id2]);
}

void upd (int x, int val) {
	for (; x < maxn; x += x&-x)
		fen[x] += val;
	return;
}

int get (int x) { 
	int res = 0;
	for (; x; x -= x&-x)
		res += fen[x];
	return res;
}

int dfs0 (int v) {
	mn[v] = IN;
	for (auto u : g[v])
		mn[v] = min(mn[v], dfs0(u));
	sort(all(g[v]), cmp);
	mn[v] = min(mn[v], v);
	return mn[v];
}

int dfs (int v, int ftime = 1, int parent = -1) {
	par[v][0] = parent;
	fins[v] = ftime;
	for (int i = 1; i < lg; i++)
		if (par[v][i - 1] + 1)
			par[v][i] = par[par[v][i - 1]][i - 1];
	for (auto u : g[v])
		ftime = dfs(u, ftime, v);
	fine[v] = ftime;
	return ftime + 1;
}

int getver (int v, int k) {
	for (int i = lg - 1; i >= 0; i--)
		if (k >= (1 << i)) {
			v = par[v][i];
			k -= (1 << i);
		}
	return v;
}

void del (int v) {
	upd(fins[v], -1);
	upd(fine[v], 1);
	s1.insert(MP(fine[v], v));
	return;
}

int main () {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	int r = -1;
	for (int i = 0; i < n; i++) {
		int p;
		cin >> p;
		--p;
		if (p == -1)
			r = i;
		else
			g[p].PB(i);
	}
	memset(par, -1, sizeof par);
	dfs0(r);
	dfs(r);
	for (int i = 0; i < n; i++)
		s1.insert(MP(fine[i], i));
	for (int i = 0; i < q; i++) {
		int type, k, v, ans = -85;
		cin >> type;
		if (type == 1) {
			cin >> k;
			for (int t = 0; t < k; t++) {
				int v = s1.begin()->S;
				ans = v;
				s1.erase(*s1.begin());
				upd(fins[v], 1);
				upd(fine[v], -1);
			}
			cout << ans + 1 << "\n";
		}
		if (type == 2) {
			cin >> v;
			--v;
			cout << get(fine[v]) << "\n";
			del(getver(v, get(fine[v])));
		}
	}
}

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