oj.uz

Submission #463470

# Submission time Handle Problem Language Result Execution time Memory
463470 2021-08-11T08:01:47 Z kilikuma Fountain (eJOI20_fountain) C++14
0 / 100
 478 ms 25160 KB 
#include <bits/stdc++.h> 
using namespace std;
struct Binary {
  int p = 0; int nbLitres = 0; 
}; 
Binary succ[100000+42][31]; 
void solve(int R, int V) {
  if (succ[R][0].p == 0) {
    printf("%d\n", 0); 
    return; 
  }
  if (V <= succ[R][0].nbLitres) {
    printf("%d\n", R); 
    return; 
  }
  if (succ[R][1].p == 0) {
    printf("%d\n", 0); 
    return; 
  }
  for (int loga = 1; loga <= 18; loga ++) {
    if (V <= succ[R][loga].nbLitres) {
      V -= succ[R][loga-1].nbLitres; 
      
      R = succ[succ[R][loga-1].p][1].p; 
     // cout << R << " " << V << endl; 
      solve(R, V); 
      
      break; 
    }
  }
  return; 
}
int main() {
  int nbReservoirs, nbRequetes; 
  scanf("%d%d",&nbReservoirs,&nbRequetes); 
  int diametre[100000+42]; int capacite[100000+42];
  for (int iReservoir = 1; iReservoir <= nbReservoirs; iReservoir ++) {
    scanf("%d%d",&diametre[iReservoir], &capacite[iReservoir]); 
  }
  // pile pour déterminer le suivant diametre
  stack<int> pile; 
  int next[100000+42]; 
  for (int iReservoir = 1; iReservoir <= nbReservoirs; iReservoir ++) {
     while ((!pile.empty()) && (diametre[pile.top()] < diametre[iReservoir])) {
       next[pile.top()] = iReservoir; 
       pile.pop(); 
     }
     pile.push(iReservoir); 
  }
  while (!pile.empty()) {
    int sommet = pile.top(); 
    next[sommet] = 0;  
    pile.pop(); 
  }
  for (int iReservoir = 1; iReservoir <= nbReservoirs; iReservoir ++) {
  // cout <<  iReservoir << " " << next[iReservoir] << endl;  
    
  }
  // binary lifting 
  for (int iReservoir = 1; iReservoir <= nbReservoirs; iReservoir ++) {
     succ[iReservoir][0].p = iReservoir; succ[iReservoir][0].nbLitres = capacite[iReservoir]; 
   //  cout << iReservoir << " " << succ[iReservoir][0].nbLitres << endl; 
  }
  for (int iReservoir = 1; iReservoir <= nbReservoirs; iReservoir ++) {
    succ[iReservoir][1].p = next[iReservoir]; succ[iReservoir][1].nbLitres = succ[iReservoir][0].nbLitres + capacite[next[iReservoir]];
 //   cout <<capacite[iReservoir] << " "; 
   // cout << iReservoir << " " << succ[iReservoir][1].nbLitres  <<  " " << next[iReservoir] << endl; 
  
  }
  for (int loga = 0; loga <= 18; loga ++) {
    succ[0][loga].p = 0; 
  }
  for (int loga = 2; loga <= 18; loga ++) {
    for (int iReservoir = 1; iReservoir <= nbReservoirs; iReservoir ++) {
       succ[iReservoir][loga].p = succ[succ[iReservoir][loga-1].p][loga-1].p; 
//      cout << succ[iReservoir][
       succ[iReservoir][loga].nbLitres = succ[iReservoir][loga-1].nbLitres + succ[succ[iReservoir][loga-1].p][loga-1].nbLitres; 
    }
  }
  for (int iRequete = 1; iRequete <= nbRequetes;iRequete++) {
    int R, V; cin >> R >> V; 
    solve(R, V); 
  }
  
}

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   scanf("%d%d",&nbReservoirs,&nbRequetes);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d%d",&diametre[iReservoir], &capacite[iReservoir]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

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

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 478 ms 25160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

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