This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |