oj.uz

Submission #463483

# Submission time Handle Problem Language Result Execution time Memory
463483 2021-08-11T08:35:34 Z kilikuma Fountain (eJOI20_fountain) C++14
100 / 100
 705 ms 26896 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 3 ms 1100 KB Output is correct
3 Correct 3 ms 1228 KB Output is correct
4 Correct 5 ms 1228 KB Output is correct
5 Correct 6 ms 1228 KB Output is correct
6 Correct 6 ms 1228 KB Output is correct
7 Correct 6 ms 1324 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 24804 KB Output is correct
2 Correct 522 ms 23056 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 3 ms 1100 KB Output is correct
3 Correct 3 ms 1228 KB Output is correct
4 Correct 5 ms 1228 KB Output is correct
5 Correct 6 ms 1228 KB Output is correct
6 Correct 6 ms 1228 KB Output is correct
7 Correct 6 ms 1324 KB Output is correct
8 Correct 455 ms 24804 KB Output is correct
9 Correct 522 ms 23056 KB Output is correct
10 Correct 6 ms 1228 KB Output is correct
11 Correct 306 ms 14984 KB Output is correct
12 Correct 705 ms 26496 KB Output is correct
13 Correct 664 ms 26472 KB Output is correct
14 Correct 589 ms 26452 KB Output is correct
15 Correct 562 ms 26896 KB Output is correct