oj.uz

Submission #876826

# Submission time Handle Problem Language Result Execution time Memory
876826 2023-11-22T11:58:26 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
7.53968 / 100
 179 ms 30404 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];
			
			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

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

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 16732 KB Output isn't correct
2 Incorrect 83 ms 21376 KB Output isn't correct
3 Incorrect 52 ms 20940 KB Output isn't correct
4 Incorrect 2 ms 16732 KB Output isn't correct
5 Incorrect 2 ms 16732 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 17240 KB Output isn't correct
10 Incorrect 17 ms 17960 KB Output isn't correct
11 Incorrect 86 ms 21332 KB Output isn't correct
12 Incorrect 56 ms 20940 KB Output isn't correct
13 Incorrect 75 ms 21200 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 19288 KB Output is correct
2 Incorrect 136 ms 26524 KB Output isn't correct
3 Incorrect 70 ms 22860 KB Output isn't correct
4 Incorrect 56 ms 20176 KB Output isn't correct
5 Incorrect 56 ms 20052 KB Output isn't correct
6 Incorrect 49 ms 19984 KB Output isn't correct
7 Incorrect 52 ms 19592 KB Output isn't correct
8 Correct 32 ms 19324 KB Output is correct
9 Incorrect 123 ms 26284 KB Output isn't correct
10 Incorrect 131 ms 26196 KB Output isn't correct
11 Incorrect 135 ms 26252 KB Output isn't correct
12 Incorrect 125 ms 25544 KB Output isn't correct
13 Correct 83 ms 27656 KB Output is correct
14 Incorrect 77 ms 22944 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 21972 KB Output isn't correct
2 Incorrect 142 ms 26068 KB Output isn't correct
3 Incorrect 120 ms 27084 KB Output isn't correct
4 Incorrect 86 ms 24824 KB Output isn't correct
5 Incorrect 87 ms 24272 KB Output isn't correct
6 Incorrect 104 ms 24812 KB Output isn't correct
7 Incorrect 114 ms 23816 KB Output isn't correct
8 Incorrect 90 ms 27088 KB Output isn't correct
9 Incorrect 140 ms 27088 KB Output isn't correct
10 Incorrect 139 ms 27084 KB Output isn't correct
11 Incorrect 144 ms 27076 KB Output isn't correct
12 Incorrect 153 ms 26392 KB Output isn't correct
13 Incorrect 162 ms 30404 KB Output isn't correct
14 Incorrect 97 ms 23372 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 179 ms 26640 KB Output isn't correct
2 Incorrect 133 ms 25240 KB Output isn't correct
3 Correct 103 ms 29064 KB Output is correct
4 Incorrect 135 ms 26224 KB Output isn't correct
5 Incorrect 143 ms 26580 KB Output isn't correct
6 Incorrect 130 ms 26372 KB Output isn't correct
7 Incorrect 151 ms 25448 KB Output isn't correct
8 Correct 95 ms 29132 KB Output is correct
9 Incorrect 66 ms 22860 KB Output isn't correct