oj.uz

Submission #628581

# Submission time Handle Problem Language Result Execution time Memory
628581 2022-08-13T13:58:53 Z mdub Fountain (eJOI20_fountain) C++14
0 / 100
 2 ms 468 KB 
#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 () {
	freopen("input.in", "r", stdin);
	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;
				 }
			 }
		 }
	 }
}

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:17:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |  freopen("input.in", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -