Submission #439356

#	Time	Username	Problem	Language	Result	Execution time	Memory
439356		NintsiChkhaidze	Fountain (eJOI20_fountain)	C++14	0 / 100	71 ms	7980 KiB

fountain

#include <iostream>
#include <queue>
#define pb push_back
using namespace std;
const int N = 100005;
int c[N],d[N],D[25][N],V[25][N],cntparent[N];
bool f[N];
deque <int> dq;
vector <int> v[N];

void dfs(int x,int par){
  f[x] = 1;
  for (int w = 1; w <= 18; w++){
    D[w][x] = D[w - 1][D[w - 1][x]];
    V[w][x] = V[w - 1][D[w - 1][x]] + V[w - 1][x] - c[D[w - 1][x]];
  }

  for (int j=0;j<v[x].size();j++){
    int to = v[x][j];
    if (to == par) continue;
    dfs(to,x);
  }
}
int get(int x,int val){
  if (c[x] >= val) return x;

  if (!f[x]) return 0;

  int ans = -1,X = x;

  for (int j = 18; j >= 0; j--){
    if (D[j][x] == 0) continue;

    if (V[j][x] <= val) {
      val -= V[j][x];
      x = D[0][D[j][x]];
      continue;
    }
    ans = D[j][x];
  }
  
  if (ans == -1) return 0;
  return ans;
}
int main() {
  int n,q;
  cin>>n>>q;

  for (int i = 1; i <= n; i++)
    cin>>d[i]>>c[i];
  
  dq.pb(d[n]);
  for (int i = n - 1; i >= 1; i--){
    while (dq.size() && d[dq.back()] <= d[i])
      dq.pop_back();
    
    if (dq.size()){
      int idx = dq.back();
      D[0][i] = idx,V[0][i] = c[idx] + c[i];
      cntparent[i]++;
      v[idx].pb(i);
    } 

    dq.push_back(i);
  }

  for (int i = 1; i <= n; i++){
    if (cntparent[i] || !v[i].size()) continue;
    dfs(i,i);
  }
  
  while(q--){
    int ind,val;
    cin>>ind>>val;
    cout<<get(ind,val)<<"\n";
  }
}

Compilation message (stderr)

fountain.cpp: In function 'void dfs(int, int)':
fountain.cpp:18:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for (int j=0;j<v[x].size();j++){
      |                ~^~~~~~~~~~~~
fountain.cpp: In function 'int get(int, int)':
fountain.cpp:29:16: warning: unused variable 'X' [-Wunused-variable]
   29 |   int ans = -1,X = x;
      |                ^

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