oj.uz

Submission #650711

# Submission time Handle Problem Language Result Execution time Memory
650711 2022-10-14T19:55:29 Z Andrei_Calota Toll (BOI17_toll) C++14
100 / 100
 203 ms 79500 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) 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; (1 << p) < n; 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 < r; rb ++ )
           for ( int re = 0; re < r; 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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 78552 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 3 ms 1364 KB Output is correct
6 Correct 4 ms 1340 KB Output is correct
7 Correct 4 ms 1364 KB Output is correct
8 Correct 102 ms 79500 KB Output is correct
9 Correct 102 ms 79432 KB Output is correct
10 Correct 73 ms 78608 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 37092 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 19 ms 1460 KB Output is correct
8 Correct 20 ms 964 KB Output is correct
9 Correct 97 ms 79420 KB Output is correct
10 Correct 147 ms 27276 KB Output is correct
11 Correct 122 ms 38828 KB Output is correct
12 Correct 101 ms 26156 KB Output is correct
13 Correct 131 ms 10316 KB Output is correct
14 Correct 87 ms 15536 KB Output is correct
15 Correct 85 ms 9144 KB Output is correct
16 Correct 85 ms 9344 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 5 ms 572 KB Output is correct
9 Correct 3 ms 576 KB Output is correct
10 Correct 85 ms 79268 KB Output is correct
11 Correct 94 ms 38504 KB Output is correct
12 Correct 125 ms 27020 KB Output is correct
13 Correct 144 ms 27272 KB Output is correct
14 Correct 124 ms 26632 KB Output is correct
15 Correct 70 ms 9160 KB Output is correct
16 Correct 70 ms 9272 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 5 ms 572 KB Output is correct
9 Correct 3 ms 576 KB Output is correct
10 Correct 85 ms 79268 KB Output is correct
11 Correct 94 ms 38504 KB Output is correct
12 Correct 125 ms 27020 KB Output is correct
13 Correct 144 ms 27272 KB Output is correct
14 Correct 124 ms 26632 KB Output is correct
15 Correct 70 ms 9160 KB Output is correct
16 Correct 70 ms 9272 KB Output is correct
17 Correct 101 ms 38616 KB Output is correct
18 Correct 1 ms 308 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 7 ms 1364 KB Output is correct
24 Correct 8 ms 852 KB Output is correct
25 Correct 11 ms 572 KB Output is correct
26 Correct 10 ms 636 KB Output is correct
27 Correct 86 ms 79356 KB Output is correct
28 Correct 133 ms 27064 KB Output is correct
29 Correct 144 ms 27272 KB Output is correct
30 Correct 119 ms 26708 KB Output is correct

Subtask #5
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 78552 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 3 ms 1364 KB Output is correct
6 Correct 4 ms 1340 KB Output is correct
7 Correct 4 ms 1364 KB Output is correct
8 Correct 102 ms 79500 KB Output is correct
9 Correct 102 ms 79432 KB Output is correct
10 Correct 73 ms 78608 KB Output is correct
11 Correct 113 ms 37092 KB Output is correct
12 Correct 1 ms 308 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 19 ms 1460 KB Output is correct
18 Correct 20 ms 964 KB Output is correct
19 Correct 97 ms 79420 KB Output is correct
20 Correct 147 ms 27276 KB Output is correct
21 Correct 122 ms 38828 KB Output is correct
22 Correct 101 ms 26156 KB Output is correct
23 Correct 131 ms 10316 KB Output is correct
24 Correct 87 ms 15536 KB Output is correct
25 Correct 85 ms 9144 KB Output is correct
26 Correct 85 ms 9344 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 2 ms 1236 KB Output is correct
33 Correct 3 ms 724 KB Output is correct
34 Correct 5 ms 572 KB Output is correct
35 Correct 3 ms 576 KB Output is correct
36 Correct 85 ms 79268 KB Output is correct
37 Correct 94 ms 38504 KB Output is correct
38 Correct 125 ms 27020 KB Output is correct
39 Correct 144 ms 27272 KB Output is correct
40 Correct 124 ms 26632 KB Output is correct
41 Correct 70 ms 9160 KB Output is correct
42 Correct 70 ms 9272 KB Output is correct
43 Correct 101 ms 38616 KB Output is correct
44 Correct 1 ms 308 KB Output is correct
45 Correct 1 ms 212 KB Output is correct
46 Correct 1 ms 212 KB Output is correct
47 Correct 1 ms 212 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 7 ms 1364 KB Output is correct
50 Correct 8 ms 852 KB Output is correct
51 Correct 11 ms 572 KB Output is correct
52 Correct 10 ms 636 KB Output is correct
53 Correct 86 ms 79356 KB Output is correct
54 Correct 133 ms 27064 KB Output is correct
55 Correct 144 ms 27272 KB Output is correct
56 Correct 119 ms 26708 KB Output is correct
57 Correct 203 ms 20824 KB Output is correct
58 Correct 101 ms 79436 KB Output is correct
59 Correct 126 ms 38808 KB Output is correct