oj.uz

답안 #872085

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
872085 2023-11-12T09:25:32 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
40.2381 / 100
 1000 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int N = 1e5 + 7, SQ = 320;
int n, q, s, t, root, h[N], st[N], sz[N], mn[N], indx[N], it[N];
vector<int> ad[N];
set<pii> ver, one[N], sq[SQ];
pii tree[N];

void input() {
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		int p;
		cin >> p;
		p--;
		if (p > -1) 
			ad[p].push_back(i);
		else
			root = i;
	}
}

void dfs(int v) {
	sz[v] = 1;
	mn[v] = v;
	st[v] = s++;
	for (int u: ad[v]) {
		h[u] = h[v] + 1;
		dfs(u);
		mn[v] = min(mn[v], mn[u]);
		sz[v] += sz[u];
	}
}

bool cmp(int u, int v) {
	return mn[u] < mn[v];
}

void forSort() {
	for (int i = 0; i < n; i++)
		sort(ad[i].begin(), ad[i].end(), cmp);
	for (int i = 0; i < n; i++)
		tree[i] = {st[i], i};
	sort(tree, tree + n);
	for (int i = 0; i < n; i++)
		it[tree[i].second] = i;
}

void dfs2(int v) {
	for (int u: ad[v])
		dfs2(u);
	indx[v] = t++;	
}

void addTo(int v) {
	for (int i = it[v]; i < it[v] + sz[v]; i++) 
		if (i % SQ || i + SQ >= it[v] + sz[v])
			one[i].insert({h[v], v});
		else {
			sq[i / SQ].insert({h[v], v});
			i += SQ - 1;
		}
}

void toErase(int v) {
	for (int i = it[v]; i < it[v] + sz[v]; i++)
		if (i % SQ || i + SQ >= it[v] + sz[v])
			one[i].erase({h[v], v});
		else {
			sq[i / SQ].erase({h[v], v});
			i += SQ - 1;
		}
}

void add(int x) {	
	while (x--) {
		pii p = *ver.begin();
		addTo(p.second);
		ver.erase(ver.begin());
		if (x == 0)
			cout << p.second + 1 << '\n';
	}
}

void output(int v) {
	int p, hi = INT_MAX, i = it[v];
	if (one[i].size()) {
		p = (*one[i].begin()).second;
		hi = h[(*one[i].begin()).second];
	}
	if (sq[i / SQ].size() && h[(*sq[i / SQ].begin()).second] < hi)
		p = (*sq[i / SQ].begin()).second;
	cout << h[v] - h[p] << '\n';
	ver.insert({indx[p], p});
	toErase(p);
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	input();
	dfs(root);
	forSort();
	dfs2(root);
	for (int i = 0; i < n; i++)
		ver.insert({indx[i], i});
	while (q--) {
		int t, v;
		cin >> t >> v;
		if (t == 1)
			add(v);
		else {
			v--;
			output(v);
		}
	}
}

Compilation message

ballmachine.cpp: In function 'void output(int)':
ballmachine.cpp:95:20: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   95 |  cout << h[v] - h[p] << '\n';
      |                 ~~~^

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 228 ms 31932 KB Output is correct
3 Correct 57 ms 14396 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 3 ms 8796 KB Output is correct
7 Correct 11 ms 9052 KB Output is correct
8 Correct 3 ms 8796 KB Output is correct
9 Correct 14 ms 10220 KB Output is correct
10 Correct 38 ms 14884 KB Output is correct
11 Correct 205 ms 31316 KB Output is correct
12 Correct 52 ms 14316 KB Output is correct
13 Correct 508 ms 16268 KB Output is correct

Subtask #2
10.7142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 12232 KB Output is correct
2 Runtime error 374 ms 131072 KB Execution killed with signal 9
3 Correct 71 ms 16728 KB Output is correct
4 Runtime error 649 ms 131072 KB Execution killed with signal 9
5 Runtime error 530 ms 131072 KB Execution killed with signal 9
6 Execution timed out 1042 ms 48432 KB Time limit exceeded
7 Runtime error 785 ms 131072 KB Execution killed with signal 9
8 Correct 26 ms 12124 KB Output is correct
9 Execution timed out 1056 ms 101780 KB Time limit exceeded
10 Runtime error 333 ms 131072 KB Execution killed with signal 9
11 Execution timed out 1030 ms 113744 KB Time limit exceeded
12 Runtime error 694 ms 131072 KB Execution killed with signal 9
13 Correct 79 ms 24492 KB Output is correct
14 Correct 76 ms 16724 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 421 ms 131072 KB Execution killed with signal 9
2 Runtime error 354 ms 131072 KB Execution killed with signal 9
3 Runtime error 298 ms 131072 KB Execution killed with signal 9
4 Runtime error 300 ms 131072 KB Execution killed with signal 9
5 Runtime error 347 ms 131072 KB Execution killed with signal 9
6 Runtime error 336 ms 131072 KB Execution killed with signal 9
7 Runtime error 347 ms 131072 KB Execution killed with signal 9
8 Runtime error 313 ms 131072 KB Execution killed with signal 9
9 Runtime error 728 ms 131072 KB Execution killed with signal 9
10 Runtime error 361 ms 131072 KB Execution killed with signal 9
11 Runtime error 355 ms 131072 KB Execution killed with signal 9
12 Runtime error 363 ms 131072 KB Execution killed with signal 9
13 Runtime error 583 ms 131072 KB Execution killed with signal 9
14 Correct 145 ms 20176 KB Output is correct

Subtask #4
1.66666666667 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1039 ms 118924 KB Time limit exceeded
2 Runtime error 336 ms 131072 KB Execution killed with signal 9
3 Correct 100 ms 26648 KB Output is correct
4 Execution timed out 1044 ms 116316 KB Time limit exceeded
5 Runtime error 339 ms 131072 KB Execution killed with signal 9
6 Execution timed out 1032 ms 34576 KB Time limit exceeded
7 Runtime error 342 ms 131072 KB Execution killed with signal 9
8 Correct 85 ms 26448 KB Output is correct
9 Correct 80 ms 16952 KB Output is correct