Submission #650709

#	Time	Username	Problem	Language	Result	Execution time	Memory
650709		Andrei_Calota	Toll (BOI17_toll)	C++14	0 / 100	112 ms	79052 KiB

toll

#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) cu rest re
void init_cost () {
   for ( int p = 0; (1 << p) < groups; p ++ )
    for ( int g = 0; g < groups; g ++ )
       for ( int rb = 0; rb < r; rb ++ )
          for ( int re = 0; re < r; re ++ )
             cost[p][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 < r; rb ++ )
      for ( int re = 0; re < r; 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..

   for ( int k = 0; k < r; k ++ )
      for ( int rb = 0; rb < r; rb ++ )
         for ( int re = 0; re < r; re ++ )
            aux[rb][re] = min (aux[rb][re], fh[rb][k] + sh[k][re] );

   for ( int rb = 0; rb < r; rb ++ )
      for ( int re = 0; re < r; 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; p < 2; p ++ )
      for ( int b = 0; b + (1 << p) < 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)][re];
              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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 8
• Subtask 4: 0 / 31
• Subtask 5: 0 / 44