Submission #628582

#	Time	Username	Problem	Language	Result	Execution time	Memory
628582		mdub	Fountain (eJOI20_fountain)	C++14	100 / 100	906 ms	28672 KiB

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