oj.uz

답안 #582793

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
582793 2022-06-24T12:30:19 Z Alan Fountain (eJOI20_fountain) C++17
100 / 100
 277 ms 32504 KB 
#include <bits/stdc++.h>
using namespace std;

struct node {
	int d, c, id;
};

int anc[100005], w[100005][20];
int lift[100005][20], lg;
vector<int> child[100005];
node ar[100005];

void dfs (int u, int p, int v) {
	lift[u][0] = p;
	w[u][0] = v;
	for (int i = 1; i <= lg; i++) {
		lift[u][i] = lift[lift[u][i-1]][i-1];
		w[u][i] = w[u][i-1] + w[lift[u][i-1]][i-1];
	}
	for (auto& v : child[u]) dfs(v, u, ar[v].c);
}

int main () {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, q, d, c, r, v;
	stack<node> st;
	cin >> n >> q;
	lg = ceil(log2(n));
	for (int i = 1; i <= n; i++) cin >> d >> c, ar[i] = {d, c, i};
	for (int i = 1; i <= n; i++) {
		while (!st.empty() && ar[i].d > st.top().d) {
			child[ar[i].id].emplace_back(st.top().id);
			st.pop();
		}
		st.push(ar[i]);
	}
	while (!st.empty()) child[0].emplace_back(st.top().id), st.pop();
	dfs(0, 0, 0);
	while (q--) {
		cin >> r >> v;
		for (int i = lg; i >= 0; i--) if (v > w[r][i]) v -= w[r][i], r = lift[r][i];
		cout << r << "\n";
	}

	return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 3 ms 2900 KB Output is correct
5 Correct 3 ms 2952 KB Output is correct
6 Correct 3 ms 2824 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 189 ms 29708 KB Output is correct
2 Correct 195 ms 28080 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 3 ms 2900 KB Output is correct
5 Correct 3 ms 2952 KB Output is correct
6 Correct 3 ms 2824 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct
8 Correct 189 ms 29708 KB Output is correct
9 Correct 195 ms 28080 KB Output is correct
10 Correct 3 ms 2820 KB Output is correct
11 Correct 68 ms 15856 KB Output is correct
12 Correct 277 ms 32504 KB Output is correct
13 Correct 179 ms 27168 KB Output is correct
14 Correct 144 ms 25504 KB Output is correct
15 Correct 107 ms 25124 KB Output is correct