Submission #463483

#	Time	Username	Problem	Language	Result	Execution time	Memory
463483		kilikuma	Fountain (eJOI20_fountain)	C++14	100 / 100	705 ms	26896 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]; 
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]); 
    succ[iReservoir][0].nbLitres = 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])) {
       succ[pile.top()][0].p = iReservoir; 
       pile.pop(); 
     }
     pile.push(iReservoir); 
  }
  while (!pile.empty()) {
    int sommet = pile.top(); 
    succ[sommet][0].p = 0;  
    pile.pop(); 
  }
  for (int iReservoir = 1; iReservoir <= nbReservoirs; iReservoir ++) {
  // cout <<  iReservoir << " " << next[iReservoir] << endl;  
    
  }
  // binary lifting 

 succ[0][0].p = 0; succ[0][0].nbLitres= 0; 
  for (int loga = 1; loga <= 18; loga ++) {
    for (int iReservoir = 0; 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; 
  //  affiche = false; 
   for (int loga = 18; loga >= 0; loga--) {
            if (succ[R][loga].nbLitres >= V) {continue;}
            V -= succ[R][loga].nbLitres;
            R = succ[R][loga].p;
           //  printf("%d\n", R); 
    }
    printf("%d\n", R); 
  //  if (! affiche) printf("%d\n", 0); 
  }
  
}

Compilation message (stderr)

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

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