Submission #582793

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
582793	2022-06-24T12:30:19 Z	Alan	Fountain (eJOI20_fountain)	C++17	100 / 100	277 ms	32504 KB

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.0 / 30.0

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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