Submission #340143

# Submission time Handle Problem Language Result Execution time Memory
340143 2020-12-27T04:03:18 Z 8e7 Editor (BOI15_edi) C++14
100 / 100
187 ms 29036 KB
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#define maxn 300005
using namespace std;
int anc[19][maxn], lev[maxn], a[maxn];
inline int getpar(int x, int hei) {
	if (lev[x] <= hei) return x;
	for (int i = 18;i >= 0;i--) {
		if (lev[anc[i][x]] > hei) x = anc[i][x];
	}
	return anc[0][x];
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++) {
		int x;
		cin >> x;
		if (x < 0) {
			lev[i] = -x;
			int z = getpar(i - 1, lev[i] - 1);
			anc[0][i] = getpar(z - 1, lev[i] - 1);
			for (int j = 1;j < 19;j++) anc[j][i] = anc[j - 1][anc[j - 1][i]];
		} else {
			a[i] = x;
		}
		cout << a[getpar(i, 0)] << "\n";
	}
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 2 ms 748 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 3 ms 876 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 3 ms 876 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 2 ms 1004 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 126 ms 28524 KB Output is correct
2 Correct 118 ms 28396 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 64 ms 8428 KB Output is correct
2 Correct 64 ms 10092 KB Output is correct
3 Correct 151 ms 21484 KB Output is correct
4 Correct 118 ms 28396 KB Output is correct
5 Correct 113 ms 29036 KB Output is correct
6 Correct 106 ms 26348 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 2 ms 748 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 3 ms 876 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 3 ms 876 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 2 ms 1004 KB Output is correct
10 Correct 126 ms 28524 KB Output is correct
11 Correct 118 ms 28396 KB Output is correct
12 Correct 64 ms 8428 KB Output is correct
13 Correct 64 ms 10092 KB Output is correct
14 Correct 151 ms 21484 KB Output is correct
15 Correct 118 ms 28396 KB Output is correct
16 Correct 113 ms 29036 KB Output is correct
17 Correct 106 ms 26348 KB Output is correct
18 Correct 112 ms 16876 KB Output is correct
19 Correct 108 ms 16876 KB Output is correct
20 Correct 187 ms 26476 KB Output is correct
21 Correct 119 ms 28396 KB Output is correct
22 Correct 114 ms 29036 KB Output is correct