oj.uz

답안 #876836

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
876836 2023-11-22T12:13:26 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
7.53968 / 100
 1000 ms 34052 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; i < n; i ++) s.insert({a[i].F, a[i].S});
	
	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 --) {
				auto cur = s.begin();
				
				int v = (*cur).S;
				upd(1, 0, n, st[v], st[v] + sz[v], 1);
				
				s.erase(cur);
				res = v;
			}
			
			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 Execution timed out 1042 ms 16984 KB Time limit exceeded
2 Execution timed out 1062 ms 23760 KB Time limit exceeded
3 Incorrect 70 ms 24268 KB Output isn't correct
4 Execution timed out 1020 ms 16728 KB Time limit exceeded
5 Execution timed out 1047 ms 16984 KB Time limit exceeded
6 Incorrect 3 ms 16984 KB Output isn't correct
7 Execution timed out 1092 ms 17040 KB Time limit exceeded
8 Execution timed out 1041 ms 16984 KB Time limit exceeded
9 Execution timed out 1045 ms 17244 KB Time limit exceeded
10 Execution timed out 1073 ms 18524 KB Time limit exceeded
11 Execution timed out 1039 ms 23676 KB Time limit exceeded
12 Incorrect 76 ms 24268 KB Output isn't correct
13 Execution timed out 1041 ms 24012 KB Time limit exceeded

Subtask #2
6.42857142857 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 20028 KB Output is correct
2 Execution timed out 1065 ms 30692 KB Time limit exceeded
3 Incorrect 103 ms 27832 KB Output isn't correct
4 Execution timed out 1035 ms 20996 KB Time limit exceeded
5 Execution timed out 1022 ms 20824 KB Time limit exceeded
6 Execution timed out 1066 ms 21028 KB Time limit exceeded
7 Execution timed out 1075 ms 20316 KB Time limit exceeded
8 Correct 33 ms 20060 KB Output is correct
9 Execution timed out 1056 ms 30604 KB Time limit exceeded
10 Execution timed out 1073 ms 30668 KB Time limit exceeded
11 Execution timed out 1056 ms 30772 KB Time limit exceeded
12 Execution timed out 1097 ms 29896 KB Time limit exceeded
13 Correct 91 ms 31692 KB Output is correct
14 Incorrect 86 ms 27772 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 66 ms 23980 KB Output isn't correct
2 Incorrect 161 ms 29712 KB Output isn't correct
3 Incorrect 112 ms 30500 KB Output isn't correct
4 Incorrect 103 ms 27904 KB Output isn't correct
5 Incorrect 105 ms 27876 KB Output isn't correct
6 Incorrect 102 ms 27856 KB Output isn't correct
7 Incorrect 117 ms 26888 KB Output isn't correct
8 Incorrect 104 ms 30444 KB Output isn't correct
9 Incorrect 156 ms 30976 KB Output isn't correct
10 Incorrect 157 ms 30932 KB Output isn't correct
11 Incorrect 154 ms 30972 KB Output isn't correct
12 Incorrect 170 ms 29828 KB Output isn't correct
13 Incorrect 159 ms 34052 KB Output isn't correct
14 Incorrect 113 ms 27876 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1056 ms 30792 KB Time limit exceeded
2 Incorrect 166 ms 29424 KB Output isn't correct
3 Correct 113 ms 33732 KB Output is correct
4 Execution timed out 1063 ms 30928 KB Time limit exceeded
5 Execution timed out 1059 ms 30664 KB Time limit exceeded
6 Execution timed out 1062 ms 30848 KB Time limit exceeded
7 Incorrect 164 ms 29392 KB Output isn't correct
8 Correct 125 ms 33736 KB Output is correct
9 Incorrect 83 ms 27664 KB Output isn't correct