oj.uz

답안 #876819

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
876819 2023-11-22T11:50:03 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
0 / 100
 154 ms 30664 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 << ' ';
		}
		
		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 << ' ';
		}
	}
	
	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 76 ms 22480 KB Output isn't correct
3 Incorrect 58 ms 22224 KB Output isn't correct
4 Incorrect 3 ms 16732 KB Output isn't correct
5 Incorrect 3 ms 16996 KB Output isn't correct
6 Incorrect 3 ms 16988 KB Output isn't correct
7 Incorrect 3 ms 16940 KB Output isn't correct
8 Incorrect 3 ms 16988 KB Output isn't correct
9 Incorrect 8 ms 17320 KB Output isn't correct
10 Incorrect 17 ms 18012 KB Output isn't correct
11 Incorrect 77 ms 22408 KB Output isn't correct
12 Incorrect 61 ms 22220 KB Output isn't correct
13 Incorrect 73 ms 22480 KB Output isn't correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 28 ms 20056 KB Output isn't correct
2 Incorrect 129 ms 27708 KB Output isn't correct
3 Incorrect 72 ms 24232 KB Output isn't correct
4 Incorrect 49 ms 20816 KB Output isn't correct
5 Incorrect 53 ms 20820 KB Output isn't correct
6 Incorrect 51 ms 20816 KB Output isn't correct
7 Incorrect 53 ms 20348 KB Output isn't correct
8 Incorrect 29 ms 20060 KB Output isn't correct
9 Incorrect 127 ms 27724 KB Output isn't correct
10 Incorrect 132 ms 27600 KB Output isn't correct
11 Incorrect 124 ms 27620 KB Output isn't correct
12 Incorrect 129 ms 26796 KB Output isn't correct
13 Incorrect 93 ms 29084 KB Output isn't correct
14 Incorrect 72 ms 24140 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 55 ms 22184 KB Output isn't correct
2 Incorrect 137 ms 26580 KB Output isn't correct
3 Incorrect 87 ms 27792 KB Output isn't correct
4 Incorrect 95 ms 25232 KB Output isn't correct
5 Incorrect 84 ms 25296 KB Output isn't correct
6 Incorrect 93 ms 25168 KB Output isn't correct
7 Incorrect 82 ms 24336 KB Output isn't correct
8 Incorrect 84 ms 27788 KB Output isn't correct
9 Incorrect 151 ms 27556 KB Output isn't correct
10 Incorrect 130 ms 27528 KB Output isn't correct
11 Incorrect 130 ms 27600 KB Output isn't correct
12 Incorrect 147 ms 26884 KB Output isn't correct
13 Incorrect 154 ms 30664 KB Output isn't correct
14 Incorrect 107 ms 24744 KB Output isn't correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 125 ms 27780 KB Output isn't correct
2 Incorrect 131 ms 26080 KB Output isn't correct
3 Incorrect 112 ms 30484 KB Output isn't correct
4 Incorrect 133 ms 28112 KB Output isn't correct
5 Incorrect 143 ms 27824 KB Output isn't correct
6 Incorrect 122 ms 27552 KB Output isn't correct
7 Incorrect 128 ms 26064 KB Output isn't correct
8 Incorrect 113 ms 30512 KB Output isn't correct
9 Incorrect 73 ms 24332 KB Output isn't correct