oj.uz

답안 #774149

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
774149 2023-07-05T12:23:15 Z Dzadzo Fountain (eJOI20_fountain) C++14
100 / 100
 223 ms 29668 KB 
#include <bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vector<int>>
#define INF INT_MAX
#define MOD 1000000009
#define MAXN 100000
using namespace std;
int p[MAXN+1][17];
int sum[MAXN+1];
vvi adj(MAXN+1);
void dfs(int v,int par,int c[]){
	if (par==-1)sum[v]=0;else sum[v]=sum[par]+c[v];
	p[v][0]=par;
	for (int i=1;i<17;i++){
		if (p[v][i-1]<1)continue;
		p[v][i]=p[p[v][i-1]][i-1];
	}
	
	for (int u:adj[v])if (u!=par)dfs(u,v,c);
}
main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	int n,q;
	cin>>n>>q;
	int d[n+1],c[n+1];
	for (int i=1;i<=n;i++)cin>>d[i]>>c[i];
	int next[n+1];
	stack<pii> s;
	for (int i=n;i>=1;i--){
		while (!s.empty() && s.top().F<=d[i])s.pop();
		if (s.empty())next[i]=0; else next[i]=s.top().S;	
		s.push({d[i],i});
	}
	
	for (int i=1;i<=n;i++){
		adj[next[i]].pb(i);
		adj[i].pb(next[i]);
	}
	memset(p,-1,sizeof(p));
	dfs(0,-1,c);
	while (q--){
		int v,vol;
		cin>>v>>vol;
		if (c[v]>=vol)cout<<v<<"\n";else{
			int cur=v;
			for (int i=16;i>=0;i--){
				if (p[cur][i]==-1 || p[cur][i]==0)continue;
				if (sum[v]-sum[p[p[cur][i]][0]]<vol)cur=p[cur][i];
			}
			cout<<p[cur][0]<<"\n";
		}
	}
}

Compilation message

fountain.cpp:27:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   27 | main() {
      | ^~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 6 ms 15956 KB Output is correct
4 Correct 6 ms 15956 KB Output is correct
5 Correct 7 ms 16084 KB Output is correct
6 Correct 7 ms 15956 KB Output is correct
7 Correct 7 ms 15992 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 158 ms 28708 KB Output is correct
2 Correct 178 ms 27872 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 6 ms 15956 KB Output is correct
4 Correct 6 ms 15956 KB Output is correct
5 Correct 7 ms 16084 KB Output is correct
6 Correct 7 ms 15956 KB Output is correct
7 Correct 7 ms 15992 KB Output is correct
8 Correct 158 ms 28708 KB Output is correct
9 Correct 178 ms 27872 KB Output is correct
10 Correct 7 ms 15956 KB Output is correct
11 Correct 72 ms 20736 KB Output is correct
12 Correct 223 ms 29668 KB Output is correct
13 Correct 176 ms 24788 KB Output is correct
14 Correct 104 ms 23888 KB Output is correct
15 Correct 71 ms 24200 KB Output is correct