oj.uz

Submission #338429

# Submission time Handle Problem Language Result Execution time Memory
338429 2020-12-23T06:04:59 Z Kevin_Zhang_TW Editor (BOI15_edi) C++17
100 / 100
 216 ms 29164 KB 
#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T>
bool chmax(T &val, T nv) {
	return val < nv ? (val = nv, true) : false;
}
template<class T>
bool chmin(T &val, T nv) {
	return nv < val ? (val = nv, true) : false;
}
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// What I should check
// 1. overflow
// 2. corner cases
// Enjoy the problem instead of hurrying to AC
// Good luck !
const int MAX_N = 300010, MAX_K = 19;

int n, state[MAX_N], par[MAX_N][MAX_K], lev[MAX_N];

int getpa(int x, int mxlev) {
	if (lev[x] <= mxlev) return x;
	for (int i = MAX_K - 1;i >= 0;--i)
		if (lev[ par[x][i] ] > mxlev) x = par[x][i];
	return par[x][0];
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 1;i <= n;++i) cin >> state[i];
	for (int i = 1;i <= n;++i) {
		if (state[i] < 0) {
			lev[i] = -state[i];
			int z = getpa(i - 1, lev[i] - 1);
			par[i][0] = getpa(z - 1, lev[i] - 1);

			for (int j = 1;j < MAX_K;++j)
				par[i][j] = par[ par[i][j-1] ][j-1];
		}
		cout << state[ getpa(i, 0) ] << '\n';
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 4 ms 876 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 3 ms 876 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 3 ms 876 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 26988 KB Output is correct
2 Correct 138 ms 27116 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 7916 KB Output is correct
2 Correct 70 ms 10348 KB Output is correct
3 Correct 175 ms 22312 KB Output is correct
4 Correct 136 ms 28396 KB Output is correct
5 Correct 128 ms 29036 KB Output is correct
6 Correct 126 ms 26312 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 4 ms 876 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 3 ms 876 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 3 ms 876 KB Output is correct
10 Correct 132 ms 26988 KB Output is correct
11 Correct 138 ms 27116 KB Output is correct
12 Correct 64 ms 7916 KB Output is correct
13 Correct 70 ms 10348 KB Output is correct
14 Correct 175 ms 22312 KB Output is correct
15 Correct 136 ms 28396 KB Output is correct
16 Correct 128 ms 29036 KB Output is correct
17 Correct 126 ms 26312 KB Output is correct
18 Correct 125 ms 17260 KB Output is correct
19 Correct 118 ms 17408 KB Output is correct
20 Correct 216 ms 27756 KB Output is correct
21 Correct 136 ms 28396 KB Output is correct
22 Correct 129 ms 29164 KB Output is correct