oj.uz

답안 #628582

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
628582 2022-08-13T14:00:42 Z mdub Fountain (eJOI20_fountain) C++14
100 / 100
 906 ms 28672 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 () {
	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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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