oj.uz

답안 #876820

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
876820 2023-11-22T11:52:01 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
0 / 100
 155 ms 29404 KB 
#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];
			
			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

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 16988 KB Output isn't correct
2 Incorrect 75 ms 21164 KB Output isn't correct
3 Incorrect 67 ms 21576 KB Output isn't correct
4 Incorrect 2 ms 16732 KB Output isn't correct
5 Incorrect 2 ms 16988 KB Output isn't correct
6 Incorrect 3 ms 16988 KB Output isn't correct
7 Incorrect 3 ms 16988 KB Output isn't correct
8 Incorrect 3 ms 16988 KB Output isn't correct
9 Incorrect 7 ms 17244 KB Output isn't correct
10 Incorrect 16 ms 18008 KB Output isn't correct
11 Incorrect 74 ms 21200 KB Output isn't correct
12 Incorrect 60 ms 21168 KB Output isn't correct
13 Incorrect 86 ms 21460 KB Output isn't correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 28 ms 19548 KB Output isn't correct
2 Incorrect 138 ms 26324 KB Output isn't correct
3 Incorrect 70 ms 23372 KB Output isn't correct
4 Incorrect 49 ms 20056 KB Output isn't correct
5 Incorrect 67 ms 20080 KB Output isn't correct
6 Incorrect 53 ms 20304 KB Output isn't correct
7 Incorrect 49 ms 19616 KB Output isn't correct
8 Incorrect 31 ms 19540 KB Output isn't correct
9 Incorrect 145 ms 26320 KB Output isn't correct
10 Incorrect 127 ms 26324 KB Output isn't correct
11 Incorrect 143 ms 26264 KB Output isn't correct
12 Incorrect 125 ms 25444 KB Output isn't correct
13 Incorrect 88 ms 28112 KB Output isn't correct
14 Incorrect 72 ms 23288 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 63 ms 21968 KB Output isn't correct
2 Incorrect 145 ms 25204 KB Output isn't correct
3 Incorrect 83 ms 26832 KB Output isn't correct
4 Incorrect 96 ms 24388 KB Output isn't correct
5 Incorrect 84 ms 24292 KB Output isn't correct
6 Incorrect 84 ms 24184 KB Output isn't correct
7 Incorrect 88 ms 23308 KB Output isn't correct
8 Incorrect 86 ms 26772 KB Output isn't correct
9 Incorrect 123 ms 26248 KB Output isn't correct
10 Incorrect 144 ms 26648 KB Output isn't correct
11 Incorrect 155 ms 26260 KB Output isn't correct
12 Incorrect 131 ms 25300 KB Output isn't correct
13 Incorrect 132 ms 29384 KB Output isn't correct
14 Incorrect 110 ms 23308 KB Output isn't correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 152 ms 26336 KB Output isn't correct
2 Incorrect 132 ms 24868 KB Output isn't correct
3 Incorrect 104 ms 29368 KB Output isn't correct
4 Incorrect 137 ms 26320 KB Output isn't correct
5 Incorrect 130 ms 26456 KB Output isn't correct
6 Incorrect 131 ms 26268 KB Output isn't correct
7 Incorrect 138 ms 25012 KB Output isn't correct
8 Incorrect 100 ms 29404 KB Output isn't correct
9 Incorrect 72 ms 23320 KB Output isn't correct