Submission #628582

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
628582	2022-08-13T14:00:42 Z	mdub	Fountain (eJOI20_fountain)	C++14	100 / 100	906 ms	28672 KB

fountain

#include <bits/stdc++.h>
using namespace std;
struct Reservoir {
	int id, diameter, capacity;
};
int n, nbQ; 
vector<Reservoir> reservoirs;
vector<vector<int>> tree;
vector<int> cumul;
void dfs(int iNode) {
	for (auto adj: tree[iNode]) {
		cumul[adj] = cumul[iNode] + reservoirs[adj].capacity;
		dfs(adj);
	}
}
int main () {
	cin >> n >> nbQ;
	reservoirs.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> reservoirs[i].diameter >> reservoirs[i].capacity;
		reservoirs[i].id = i;
	}
	
	stack<Reservoir> maximums;
	maximums.push({n, int(1e9) + 1, int(1e9) + 1});
	tree.resize(n + 1);
	vector<vector<int>> ancestors(n + 1, vector<int>(log2(n) + 2, n));
	for (int i = n - 1; i >= 0; i--) {
		while (reservoirs[i].diameter >= maximums.top().diameter) {
			maximums.pop();
		}
		tree[maximums.top().id].push_back(reservoirs[i].id);
		ancestors[reservoirs[i].id][0] = maximums.top().id;
		maximums.push({i, reservoirs[i].diameter, reservoirs[i].capacity});
	}
	cumul.resize(n + 1);
	cumul[n] = 0;
	
	
	dfs(n);
	for (int i = 1; i <= log2(n) + 1; i++) {
		for (int iNode = 0; iNode < n; iNode++) {
			ancestors[iNode][i] = ancestors[ancestors[iNode][i-1]][i-1];
		}
	}
	
	for (int iQ = 0; iQ < nbQ; iQ++) {
		int cur, vol; cin >> cur >> vol;
		cur--;
		bool done = false;
		cumul[n] = -int(1e9)-1;
		while (!done) {
			for (int i = 0; i <= log2(n) + 1; i++) {
				if (cumul[cur] - cumul[ancestors[cur][i]] >= vol) {
					 if (!i) {
						 if (cur == n-1) cout << 0 << '\n';
						 else cout << cur + 1 << '\n';
						 done = true;
					 }
					 else {
						 vol -= cumul[cur] - cumul[ancestors[cur][i-1]];
						 cur = ancestors[cur][i-1];
					 }
					 break;
				 }
			 }
		 }
	 }
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	2 ms	308 KB	Output is correct
4	Correct	4 ms	436 KB	Output is correct
5	Correct	6 ms	468 KB	Output is correct
6	Correct	5 ms	468 KB	Output is correct
7	Correct	5 ms	444 KB	Output is correct

Subtask #2

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	556 ms	25884 KB	Output is correct
2	Correct	627 ms	24540 KB	Output is correct

Subtask #3

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	2 ms	308 KB	Output is correct
4	Correct	4 ms	436 KB	Output is correct
5	Correct	6 ms	468 KB	Output is correct
6	Correct	5 ms	468 KB	Output is correct
7	Correct	5 ms	444 KB	Output is correct
8	Correct	556 ms	25884 KB	Output is correct
9	Correct	627 ms	24540 KB	Output is correct
10	Correct	5 ms	444 KB	Output is correct
11	Correct	300 ms	12024 KB	Output is correct
12	Correct	906 ms	28672 KB	Output is correct
13	Correct	682 ms	22092 KB	Output is correct
14	Correct	482 ms	20408 KB	Output is correct
15	Correct	455 ms	19304 KB	Output is correct