Submission #384985

#	Time	Username	Problem	Language	Result	Execution time	Memory
384985		antontsiorvas	Fountain (eJOI20_fountain)	C++14	0 / 100	191 ms	26860 KiB

fountain

#include <cstdio>
#include <vector>
#include <cmath>
#include <stack>
using namespace std;

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

void dfs(int v, int prev, int d, int h){
	tin[v] = ++timer;
	up[v][0] = prev;
	height[v] = h;
	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],h+1);
	}
	tout[v] = ++timer;
}

bool is_ancestor(int a, int b){	return tin[a] <= tin[b] && tout[b] <= tout[a];	}

int lca(int a, int b){
	if(is_ancestor(a,b)) return a;
	if(is_ancestor(b,a)) return b;
	
	for(int i=l; i>=0; i--){
		if(!is_ancestor(up[a][i],b)){
			a = up[a][i];
		}
	}
	
	return up[a][0];
}

void fill(){
	int ancestor = l;
	while(ancestor >= 0 && node != 0 && water > 0){
		if(capacity[node] >= water){
			printf("%d\n",node);
			return;
		}
		while(dist[node] - dist[up[node][ancestor]] > water && ancestor >= 0) ancestor--;
		if(ancestor == -1){
			printf("%d\n",node);
			return;
		}
		water -= dist[node]-dist[up[node][ancestor]];
		node = up[node][ancestor];
	}
	
	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,0);
	
	while(Q--){
		scanf("%d%d",&node,&water);
		fill();
	}
}

Compilation message (stderr)

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

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40