oj.uz

답안 #117119

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
117119 2019-06-14T22:27:39 Z MB81 Ball Machine (BOI13_ballmachine) C++11
100 / 100
 371 ms 26232 KB 
#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.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 9856 KB Output is correct
2 Correct 167 ms 15960 KB Output is correct
3 Correct 92 ms 15608 KB Output is correct
4 Correct 9 ms 9728 KB Output is correct
5 Correct 10 ms 9856 KB Output is correct
6 Correct 11 ms 9856 KB Output is correct
7 Correct 10 ms 9856 KB Output is correct
8 Correct 11 ms 9856 KB Output is correct
9 Correct 17 ms 10240 KB Output is correct
10 Correct 37 ms 11256 KB Output is correct
11 Correct 174 ms 15352 KB Output is correct
12 Correct 100 ms 15608 KB Output is correct
13 Correct 148 ms 15096 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 13124 KB Output is correct
2 Correct 241 ms 21404 KB Output is correct
3 Correct 138 ms 17652 KB Output is correct
4 Correct 105 ms 13636 KB Output is correct
5 Correct 110 ms 13588 KB Output is correct
6 Correct 86 ms 13560 KB Output is correct
7 Correct 91 ms 12792 KB Output is correct
8 Correct 52 ms 13176 KB Output is correct
9 Correct 224 ms 21724 KB Output is correct
10 Correct 268 ms 21496 KB Output is correct
11 Correct 217 ms 21228 KB Output is correct
12 Correct 247 ms 19624 KB Output is correct
13 Correct 371 ms 23928 KB Output is correct
14 Correct 124 ms 17624 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 16252 KB Output is correct
2 Correct 279 ms 20120 KB Output is correct
3 Correct 189 ms 22808 KB Output is correct
4 Correct 188 ms 19748 KB Output is correct
5 Correct 180 ms 19156 KB Output is correct
6 Correct 188 ms 19156 KB Output is correct
7 Correct 195 ms 17956 KB Output is correct
8 Correct 204 ms 22924 KB Output is correct
9 Correct 291 ms 22136 KB Output is correct
10 Correct 278 ms 21852 KB Output is correct
11 Correct 279 ms 21752 KB Output is correct
12 Correct 273 ms 20128 KB Output is correct
13 Correct 300 ms 26232 KB Output is correct
14 Correct 203 ms 18420 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 271 ms 22740 KB Output is correct
2 Correct 287 ms 20088 KB Output is correct
3 Correct 188 ms 25624 KB Output is correct
4 Correct 271 ms 22668 KB Output is correct
5 Correct 273 ms 21568 KB Output is correct
6 Correct 325 ms 21368 KB Output is correct
7 Correct 286 ms 20084 KB Output is correct
8 Correct 190 ms 25848 KB Output is correct
9 Correct 116 ms 17648 KB Output is correct