Submission #582793

#	Time	Username	Problem	Language	Result	Execution time	Memory
582793		Alan	Fountain (eJOI20_fountain)	C++17	100 / 100	277 ms	32504 KiB

fountain

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40