oj.uz

Submission #650506

# Submission time Handle Problem Language Result Execution time Memory
650506 2022-10-14T06:59:47 Z Andrei_Calota Toll (BOI17_toll) C++14
0 / 100
 204 ms 73164 KB 
#include <bits/stdc++.h>

using namespace std;
const int NMAX = 5e4;
const int RMAX = 5;
const int LOG_MAX = 16;
const int INF = 1e9;
const int NONE = -1;

int r, n, m, q;
int groups;
static inline int group ( int node ) {
    return node / r;
}
static inline int spot ( int node ) {
   return node % r;
}

int cost[LOG_MAX][NMAX][RMAX][RMAX];
/// cost[p][g][rb][re] = costului minim
/// pentru un drum de lungime (1<<p) care incepe
/// din grupa g cu rest rb si se termina
/// in grupa g + (1<<p) - 1 cu rest re
void init_cost () {
    for ( int g = 0; g < groups; g ++ )
       for ( int rb = 0; rb < r; rb ++ )
          for ( int re = 0; re < r; re ++ )
             cost[0][g][rb][re] = INF;
}
void merge_answer ( int answer[RMAX][RMAX], int fh[RMAX][RMAX], int sh[RMAX][RMAX] ) {
   int aux[RMAX][RMAX];
   for ( int rb = 0; rb < RMAX; rb ++ )
      for ( int re = 0; re < RMAX; re ++ )
         aux[rb][re] = INF;


   /// obs : in drumul de la grupa x la grupa y
   /// se trece prin toate grupele de la x, x + 1..y
   for ( int k = 0; k < RMAX; k ++ )
      for ( int rb = 0; rb < RMAX; rb ++ )
         for ( int re = 0; re < RMAX; re ++ )
            aux[rb][re] = min (aux[rb][re], fh[rb][k] + sh[k][re] );
   for ( int rb = 0; rb < RMAX; rb ++ )
      for ( int re = 0; re < RMAX; re ++ )
         answer[rb][re] = aux[rb][re];
}
void query ( int aux[RMAX][RMAX], int start, int stop ) {
   for ( int bit = LOG_MAX - 1; bit >= 0; bit -- ) {
      if ( start + (1 << bit) <= stop ) {
        merge_answer ( aux, aux, cost[bit][start] );
        start += (1 << bit);
      }
   }
}

int main()
{
   cin >> r >> n >> m >> q;
   groups = (n + r - 1) / r;
   init_cost ();
   for ( int indx = 0; indx < m; indx ++ ) {
      int a, b, t; cin >> a >> b >> t;
      cost[0][group (a)][spot (a)][spot (b)] = t;
   }

   for ( int p = 1; (1 << p) < groups; p ++ )
      for ( int b = 0; b + (1 << p) - 1 < groups; b ++ )
         merge_answer (cost[p][b], cost[p - 1][b], cost[p - 1][b + (1 << (p - 1))]);
   for ( int indx = 0; indx < q; indx ++ ) {
      int a, b; cin >> a >> b;

      if ( group (a) == group (b) )
        cout << NONE;
      else {
        int aux[RMAX][RMAX];
        for ( int rb = 0; rb < RMAX; rb ++ )
           for ( int re = 0; re < RMAX; re ++ )
              if ( rb == spot (a) )
                aux[rb][re] = cost[0][group (a)][spot (a)][spot (b)];
              else
                aux[rb][re] = INF;
        query ( aux, group (a) + 1, group (b) );
        if ( aux[spot (a)][spot (b)] == INF )
          cout << NONE;
        else
          cout << aux[spot (a)][spot (b)];
      }
      cout << "\n";
   }
    return 0;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

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