oj.uz

Submission #439401

# Submission time Handle Problem Language Result Execution time Memory
439401 2021-06-29T18:11:03 Z NintsiChkhaidze Fountain (eJOI20_fountain) C++14
100 / 100
 999 ms 47208 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 (c[x] >= val) return x;
  if (!f[x]) return 0;
  
  int ans = -1;
  for (int j = 18; j >= 0; j--){
    if (D[j][x] == 0) continue;

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

  for (int i = 1; i <= n; i++)
    cin>>d[i]>>c[i];
  
  dq.pb(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()) dfs(i);
  
  while(t--){
    int ind,val;
    cin>>ind>>val;
    cout<<get(ind,val)<<"\n";
  }
}

Compilation message

fountain.cpp: In function 'void dfs(long long int)':
fountain.cpp:20:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   for (int j=0;j<v[x].size();j++)
      |                ~^~~~~~~~~~~~
fountain.cpp: At global scope:
fountain.cpp:44:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   44 | main() {
      | ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 3 ms 3020 KB Output is correct
3 Correct 5 ms 3060 KB Output is correct
4 Correct 6 ms 3172 KB Output is correct
5 Correct 9 ms 3276 KB Output is correct
6 Correct 8 ms 3148 KB Output is correct
7 Correct 9 ms 3148 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 40860 KB Output is correct
2 Correct 767 ms 41012 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 3 ms 3020 KB Output is correct
3 Correct 5 ms 3060 KB Output is correct
4 Correct 6 ms 3172 KB Output is correct
5 Correct 9 ms 3276 KB Output is correct
6 Correct 8 ms 3148 KB Output is correct
7 Correct 9 ms 3148 KB Output is correct
8 Correct 645 ms 40860 KB Output is correct
9 Correct 767 ms 41012 KB Output is correct
10 Correct 8 ms 3148 KB Output is correct
11 Correct 352 ms 24596 KB Output is correct
12 Correct 999 ms 47208 KB Output is correct
13 Correct 855 ms 42436 KB Output is correct
14 Correct 665 ms 41084 KB Output is correct
15 Correct 641 ms 39592 KB Output is correct