#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
const int NM = 50000;
const ll INF = 1e18;
struct matrix{
int M, N;
ll grid[5][5];
void init(int x, int y, ll val){
M = x, N = y;
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
grid[i][j] = val;
}
matrix operator * (matrix b){
matrix a = *this;
matrix c;
c.init(a.M, b.N, +INF);
for (int i = 0; i < c.M; i++)
for (int j = 0; j < c.N; j++)
for (int k = 0; k < a.N; k++)
c.grid[i][j] = min(c.grid[i][j], a.grid[i][k]+b.grid[k][j]);
return c;
}
};
int K, N, M, O, nLayer;
map <pii, ll> d;
matrix A[NM+5];
matrix st[4*NM+5];
ll dist(int a, int b){
if (a == b) return 0;
if (d.count(mp(a, b)) == 0) return +INF;
return d[mp(a, b)];
}
matrix iden(int k){
matrix a;
a.init(k, k, +INF);
for (int i = 0; i < k; i++)
a.grid[i][i] = 0;
return a;
}
void build(int id, int l, int r){
st[id].init(K, K, 0);
if (l == r){
st[id] = A[l];
return;
}
int mid = (l+r)/2;
build(2*id, l, mid);
build(2*id+1, mid+1, r);
st[id] = st[2*id]*st[2*id+1];
}
matrix get(int id, int l, int r, int u, int v){
if (u > v || v < l || u > r) return iden(K);
if (l >= u && r <= v) return st[id];
int mid = (l+r)/2;
return get(2*id, l, mid, u, v)*get(2*id+1, mid+1, r, u, v);
}
void solveQuery(int a, int b){
int l = a/K, r = b/K;
if (l >= r){
cout << "-1\n";
return;
}
matrix C; C.init(1, K, +INF);
for (int i = 0; i < K; i++)
C.grid[0][i] = dist(a, (l+1)*K+i);
C = C*get(1, 0, nLayer-2, l+1, r-1);
ll ans = C.grid[0][b%K];
if (ans >= +INF) ans = -1;
cout << ans << "\n";
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> K >> N >> M >> O;
nLayer = N/K+(N%K > 0);
for (int i = 0; i <= nLayer-2; i++)
A[i].init(K, K, +INF);
while (M--){
int a, b; ll t;
cin >> a >> b >> t;
d[mp(a, b)] = t;
A[a/K].grid[a%K][b%K] = t;
}
build(1, 0, nLayer-2);
while (O--){
int a, b;
cin >> a >> b;
solveQuery(a, b);
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
78 ms |
40328 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
2 ms |
980 KB |
Output is correct |
6 |
Correct |
2 ms |
980 KB |
Output is correct |
7 |
Correct |
3 ms |
980 KB |
Output is correct |
8 |
Correct |
69 ms |
40316 KB |
Output is correct |
9 |
Correct |
71 ms |
40116 KB |
Output is correct |
10 |
Correct |
35 ms |
37252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
99 ms |
24688 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
10 ms |
1032 KB |
Output is correct |
8 |
Correct |
12 ms |
800 KB |
Output is correct |
9 |
Correct |
64 ms |
40316 KB |
Output is correct |
10 |
Correct |
131 ms |
20168 KB |
Output is correct |
11 |
Correct |
120 ms |
25108 KB |
Output is correct |
12 |
Correct |
78 ms |
16224 KB |
Output is correct |
13 |
Correct |
124 ms |
14284 KB |
Output is correct |
14 |
Correct |
69 ms |
14672 KB |
Output is correct |
15 |
Correct |
64 ms |
9604 KB |
Output is correct |
16 |
Correct |
71 ms |
9548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 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 |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
3 ms |
724 KB |
Output is correct |
9 |
Correct |
2 ms |
596 KB |
Output is correct |
10 |
Correct |
49 ms |
40220 KB |
Output is correct |
11 |
Correct |
74 ms |
24668 KB |
Output is correct |
12 |
Correct |
134 ms |
19972 KB |
Output is correct |
13 |
Correct |
120 ms |
20924 KB |
Output is correct |
14 |
Correct |
87 ms |
18508 KB |
Output is correct |
15 |
Correct |
46 ms |
9556 KB |
Output is correct |
16 |
Correct |
49 ms |
9676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 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 |
1 ms |
980 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
3 ms |
724 KB |
Output is correct |
9 |
Correct |
2 ms |
596 KB |
Output is correct |
10 |
Correct |
49 ms |
40220 KB |
Output is correct |
11 |
Correct |
74 ms |
24668 KB |
Output is correct |
12 |
Correct |
134 ms |
19972 KB |
Output is correct |
13 |
Correct |
120 ms |
20924 KB |
Output is correct |
14 |
Correct |
87 ms |
18508 KB |
Output is correct |
15 |
Correct |
46 ms |
9556 KB |
Output is correct |
16 |
Correct |
49 ms |
9676 KB |
Output is correct |
17 |
Correct |
82 ms |
24624 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
4 ms |
980 KB |
Output is correct |
24 |
Correct |
4 ms |
724 KB |
Output is correct |
25 |
Correct |
11 ms |
748 KB |
Output is correct |
26 |
Correct |
8 ms |
596 KB |
Output is correct |
27 |
Correct |
60 ms |
40192 KB |
Output is correct |
28 |
Correct |
112 ms |
19908 KB |
Output is correct |
29 |
Correct |
151 ms |
20932 KB |
Output is correct |
30 |
Correct |
98 ms |
18540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
78 ms |
40328 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
2 ms |
980 KB |
Output is correct |
6 |
Correct |
2 ms |
980 KB |
Output is correct |
7 |
Correct |
3 ms |
980 KB |
Output is correct |
8 |
Correct |
69 ms |
40316 KB |
Output is correct |
9 |
Correct |
71 ms |
40116 KB |
Output is correct |
10 |
Correct |
35 ms |
37252 KB |
Output is correct |
11 |
Correct |
99 ms |
24688 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
10 ms |
1032 KB |
Output is correct |
18 |
Correct |
12 ms |
800 KB |
Output is correct |
19 |
Correct |
64 ms |
40316 KB |
Output is correct |
20 |
Correct |
131 ms |
20168 KB |
Output is correct |
21 |
Correct |
120 ms |
25108 KB |
Output is correct |
22 |
Correct |
78 ms |
16224 KB |
Output is correct |
23 |
Correct |
124 ms |
14284 KB |
Output is correct |
24 |
Correct |
69 ms |
14672 KB |
Output is correct |
25 |
Correct |
64 ms |
9604 KB |
Output is correct |
26 |
Correct |
71 ms |
9548 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
0 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 |
1 ms |
980 KB |
Output is correct |
33 |
Correct |
1 ms |
724 KB |
Output is correct |
34 |
Correct |
3 ms |
724 KB |
Output is correct |
35 |
Correct |
2 ms |
596 KB |
Output is correct |
36 |
Correct |
49 ms |
40220 KB |
Output is correct |
37 |
Correct |
74 ms |
24668 KB |
Output is correct |
38 |
Correct |
134 ms |
19972 KB |
Output is correct |
39 |
Correct |
120 ms |
20924 KB |
Output is correct |
40 |
Correct |
87 ms |
18508 KB |
Output is correct |
41 |
Correct |
46 ms |
9556 KB |
Output is correct |
42 |
Correct |
49 ms |
9676 KB |
Output is correct |
43 |
Correct |
82 ms |
24624 KB |
Output is correct |
44 |
Correct |
1 ms |
212 KB |
Output is correct |
45 |
Correct |
0 ms |
212 KB |
Output is correct |
46 |
Correct |
0 ms |
212 KB |
Output is correct |
47 |
Correct |
0 ms |
212 KB |
Output is correct |
48 |
Correct |
0 ms |
212 KB |
Output is correct |
49 |
Correct |
4 ms |
980 KB |
Output is correct |
50 |
Correct |
4 ms |
724 KB |
Output is correct |
51 |
Correct |
11 ms |
748 KB |
Output is correct |
52 |
Correct |
8 ms |
596 KB |
Output is correct |
53 |
Correct |
60 ms |
40192 KB |
Output is correct |
54 |
Correct |
112 ms |
19908 KB |
Output is correct |
55 |
Correct |
151 ms |
20932 KB |
Output is correct |
56 |
Correct |
98 ms |
18540 KB |
Output is correct |
57 |
Correct |
212 ms |
22016 KB |
Output is correct |
58 |
Correct |
67 ms |
40428 KB |
Output is correct |
59 |
Correct |
100 ms |
25108 KB |
Output is correct |