oj.uz

Submission #439371

# Submission time Handle Problem Language Result Execution time Memory
439371 2021-06-29T17:29:02 Z NintsiChkhaidze Fountain (eJOI20_fountain) C++14
0 / 100
 73 ms 6600 KB 
#include <iostream>
#include <queue>
#define pb push_back
#define ll long long
//#define int ll
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){
  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++)
    dfs(v[x][j]);
}
int get(int x,int val){
  if (!f[x]) {
      if (c[x] >= val) return x;
      return 0;
  }

  int ans = -1,X = x,q = 0;
  
  for (int j = 18; j >= 0; j--){
    if (D[j][x] == 0) continue;

    if (V[j][x] <= val) {
      q = 1;
      val -= V[j][x];
      if (val == 0) {ans = D[j][x]; break;}
      x = D[0][D[j][x]];
      continue;
    }
    ans = D[j][x];
  }
  
  if (!q && c[x] >= val) ans = 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);
  }
  
  while(q--){
    int ind,val;
    cin>>ind>>val;
    cout<<get(ind,val)<<"\n";
  }
}

Compilation message

fountain.cpp: In function 'void dfs(int)':
fountain.cpp:20:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   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,q = 0;
      |                ^

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Incorrect 3 ms 2892 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 73 ms 6600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Incorrect 3 ms 2892 KB Output isn't correct
3 Halted 0 ms 0 KB -