Submission #463474

#	Time	Username	Problem	Language	Result	Execution time	Memory
463474		kilikuma	Fountain (eJOI20_fountain)	C++14	0 / 100	471 ms	25460 KiB

fountain

#include <bits/stdc++.h> 
using namespace std;
struct Binary {
  int p = 0; int nbLitres = 0; 
}; 
bool affiche = false; 
Binary succ[100000+42][31]; 
void solve(int R, int V) {
   if (succ[R][0].p == 0) {
    printf("%d\n", 0); 
   //  affiche =true;
    return; 
  }
  if (V <= succ[R][0].nbLitres) {
    printf("%d\n", R); 
    // affiche = true; 
    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); 
      return;
     
    }
  }
  printf("%d\n", 0); 
  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; 
      if (succ[iReservoir][loga].p == 0){
        succ[iReservoir][loga].nbLitres = succ[iReservoir][loga-1].nbLitres; 
      }
      else 
//      cout << succ[iReservoir][
       succ[iReservoir][loga].nbLitres = succ[iReservoir][loga-1].nbLitres + succ[succ[iReservoir][loga-1].p][loga-1].nbLitres; 
    }
  }
   for (int loga = 0; loga <= 18; loga ++) {
    succ[0][loga].p = 0; 
  }
  for (int iRequete = 1; iRequete <= nbRequetes;iRequete++) {
    int R, V; cin >> R >> V; 
  //  affiche = false; 
    solve(R, V); 
  //  if (! affiche) printf("%d\n", 0); 
  }
  
}

Compilation message (stderr)

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

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