oj.uz

Submission #384986

# Submission time Handle Problem Language Result Execution time Memory
384986 2021-04-02T20:09:59 Z antontsiorvas Fountain (eJOI20_fountain) C++14
100 / 100
 284 ms 26732 KB 
#include <cstdio>
#include <vector>
#include <cmath>
#include <stack>
using namespace std;

int N, Q, diameter[100005], capacity[100005], dist[100005], up[100005][20], l, anc[20];
vector<int> edges[100005];
stack<int> st;
int node, water; 

void dfs(int v, int prev, int d){
	up[v][0] = prev;
	dist[v] = d + capacity[v];
	for(int i=1; i<=l; i++) up[v][i] = up[up[v][i-1]][i-1];
	for(int u : edges[v]){
		if(u == prev) continue;
		dfs(u,v,dist[v]);
	}
}

void fill(){
	for(int i=l; i>=0; i--){
		if(dist[node] - dist[up[node][i]] >= water) continue;
		water -= dist[node] - dist[up[node][i]];
		node = up[node][i];
	}
	printf("%d\n",node);
}

int main(){
	scanf("%d%d",&N,&Q);
	for(int i=1; i<=N; i++) scanf("%d%d",&diameter[i],&capacity[i]);
	diameter[0] = 2000000000;
//	capacity[0] = 2000000000;
	st.push(0);
	for(int i=N; i>0; i--){
		while(diameter[st.top()] <= diameter[i]) st.pop();
		edges[st.top()].push_back(i);
		st.push(i);
	}
	l = ceil(log2(N));
	
	anc[0] = 1;
	for(int i=1; i<=l; i++) anc[i] = anc[i-1]*2;
	dfs(0,0,0);
	
	while(Q--){
		scanf("%d%d",&node,&water);
		fill();
	}
}

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   32 |  scanf("%d%d",&N,&Q);
      |  ~~~~~^~~~~~~~~~~~~~
fountain.cpp:33:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |  for(int i=1; i<=N; i++) scanf("%d%d",&diameter[i],&capacity[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |   scanf("%d%d",&node,&water);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 3 ms 2796 KB Output is correct
3 Correct 3 ms 2796 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 4 ms 2924 KB Output is correct
6 Correct 4 ms 2796 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 21484 KB Output is correct
2 Correct 216 ms 23148 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 3 ms 2796 KB Output is correct
3 Correct 3 ms 2796 KB Output is correct
4 Correct 3 ms 2796 KB Output is correct
5 Correct 4 ms 2924 KB Output is correct
6 Correct 4 ms 2796 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 180 ms 21484 KB Output is correct
9 Correct 216 ms 23148 KB Output is correct
10 Correct 4 ms 2796 KB Output is correct
11 Correct 82 ms 11756 KB Output is correct
12 Correct 284 ms 26732 KB Output is correct
13 Correct 215 ms 19752 KB Output is correct
14 Correct 155 ms 17900 KB Output is correct
15 Correct 132 ms 16684 KB Output is correct