oj.uz

답안 #245255

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
245255 2020-07-05T20:58:12 Z super_j6 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 208 ms 24184 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int mxn = 100001, k = __lg(mxn) + 1;

struct BIT{
	int bit[mxn];
	
	BIT(){
		memset(bit, 0, sizeof(bit));
	}
	
	void add(int x, int v){
		for(x++; x < mxn; x += x & -x) bit[x] += v;
	}
	
	int qry(){
		int ret = 0, s = 0;
		for(int i = k - 1; ~i; i--){
			ret |= 1 << i;
			if(ret >= mxn || bit[ret] + s < ret) ret ^= 1 << i;
			else s += bit[ret];
		}
		return ret;
	}
};

int n, q;
int mn[mxn], id[mxn], rid[mxn], vis[mxn];
int p[k][mxn];
vector<int> g[mxn];
BIT bit;
int rt, tt;

int dfs(int c){
	mn[c] = c;
	for(int i = 1; i < k; i++) p[i][c] = ~p[i - 1][c] ? p[i - 1][p[i - 1][c]] : -1;
	for(int i : g[c]) mn[c] = min(mn[c], dfs(i));
	return mn[c];
}

void dfs2(int c){
	sort(g[c].begin(), g[c].end(), [&](int x, int y){
		return mn[x] < mn[y];	
	});
	for(int i : g[c]) dfs2(i);
	rid[id[c] = tt++] = c;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> q;
	
	for(int i = 0; i < n; i++){
		cin >> p[0][i];
		g[--p[0][i]].push_back(i);
		if(!~p[0][i]) rt = i;
	}
	
	dfs(rt);
	dfs2(rt);
	
	while(q--){
		int t, x;
		cin >> t >> x;
		if(!~-t){
			int c = -1;
			while(x--){
				c = bit.qry();
				vis[rid[c]] = 1;
				bit.add(c, 1);
			}
			cout << rid[c] + 1 << endl;
		}else{
			x--;
			int ret = 0;
			for(int i = k - 1; ~i; i--){
				if(~p[i][x] && vis[p[i][x]]){
					ret |= 1 << i;
					x = p[i][x];
				}
			}
			vis[x] = 0;
			bit.add(id[x], -1);
			cout << ret << endl;
		}
	}

	return 0;
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 3200 KB Output is correct
2 Correct 87 ms 11004 KB Output is correct
3 Correct 63 ms 10744 KB Output is correct
4 Correct 6 ms 3200 KB Output is correct
5 Correct 6 ms 3200 KB Output is correct
6 Correct 8 ms 3328 KB Output is correct
7 Correct 7 ms 3328 KB Output is correct
8 Correct 7 ms 3328 KB Output is correct
9 Correct 11 ms 3712 KB Output is correct
10 Correct 20 ms 5120 KB Output is correct
11 Correct 86 ms 10872 KB Output is correct
12 Correct 67 ms 10876 KB Output is correct
13 Correct 87 ms 10988 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 7424 KB Output is correct
2 Correct 152 ms 18680 KB Output is correct
3 Correct 78 ms 13556 KB Output is correct
4 Correct 56 ms 8440 KB Output is correct
5 Correct 59 ms 8312 KB Output is correct
6 Correct 52 ms 8312 KB Output is correct
7 Correct 50 ms 7424 KB Output is correct
8 Correct 36 ms 7416 KB Output is correct
9 Correct 145 ms 19192 KB Output is correct
10 Correct 146 ms 18684 KB Output is correct
11 Correct 141 ms 18680 KB Output is correct
12 Correct 151 ms 16632 KB Output is correct
13 Correct 121 ms 21244 KB Output is correct
14 Correct 86 ms 13428 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 11256 KB Output is correct
2 Correct 175 ms 16888 KB Output is correct
3 Correct 139 ms 19704 KB Output is correct
4 Correct 115 ms 15984 KB Output is correct
5 Correct 112 ms 15608 KB Output is correct
6 Correct 112 ms 15608 KB Output is correct
7 Correct 109 ms 14072 KB Output is correct
8 Correct 132 ms 19832 KB Output is correct
9 Correct 164 ms 19320 KB Output is correct
10 Correct 180 ms 18936 KB Output is correct
11 Correct 171 ms 18936 KB Output is correct
12 Correct 168 ms 16892 KB Output is correct
13 Correct 208 ms 24184 KB Output is correct
14 Correct 117 ms 14516 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 192 ms 19448 KB Output is correct
2 Correct 181 ms 17016 KB Output is correct
3 Correct 134 ms 23544 KB Output is correct
4 Correct 184 ms 19448 KB Output is correct
5 Correct 171 ms 18936 KB Output is correct
6 Correct 149 ms 18808 KB Output is correct
7 Correct 175 ms 16888 KB Output is correct
8 Correct 124 ms 23544 KB Output is correct
9 Correct 80 ms 13556 KB Output is correct