///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define append push_back
#define add insert
#define nl "\n"
#define ff first
#define ss second
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL)
#define N 50000
int k,M;
int a[N][5][5];
vector<vector<int>> g;
vector<vector<int>> seg[4*N];
void build(int v=1,int s=0,int e=M){
seg[v]=g;
for(int i=0;i<k;i++)
for(int j=0;j<k;j++)
seg[v][i][j]=5e8;
if(e-s==1){
for(int i=0;i<k;i++)
seg[v][i][i]=0;
return;
}
int mid,rc,lc;
mid=(s+e)/2;
rc=2*v+1;
lc=2*v;
build(lc,s,mid);
build(rc,mid,e);
for(int i=0;i<k;i++)
for(int j=0;j<k;j++)
for(int l=0;l<k;l++)
for(int r=0;r<k;r++)
seg[v][i][j]=min(seg[v][i][j],
seg[lc][i][l]+a[mid-1][l][r]+seg[rc][r][j]);
}
vector<vector<int>> get(int l,int r,int v=1,int s=0,int e=M){
if(r<=s || e<=l) return g;
if(l<=s && e<=r) return seg[v];
vector<vector<int>> o,p,q;
int mid,rc,lc;
mid=(s+e)/2;
rc=2*v+1;
lc=2*v;
p=get(l,r,lc,s,mid);
q=get(l,r,rc,mid,e);
o=g;
if(mid>=r) return p;
if(mid<=l) return q;
for(int i=0;i<k;i++)
for(int j=0;j<k;j++)
o[i][j]=5e8;
for(int i=0;i<k;i++)
for(int j=0;j<k;j++)
for(int l=0;l<k;l++)
for(int r=0;r<k;r++)
o[i][j]=min(o[i][j],
p[i][l]+a[mid-1][l][r]+q[r][j]);
return o;
}
void solve(){
int n,m,o,p,q,r;
cin>>k>>n>>m>>o;
M=(n+k-1)/k;
for(int i=0;i<k;i++){
vector<int> u;
for(int j=0;j<k;j++)
u.append(0);
g.append(u);
}
for(int i=0;i<m;i++){
cin>>p>>q>>r;
a[p/k][p%k][q%k]=r;
}
for(int i=0;i<M;i++)
for(int j=0;j<k;j++)
for(int l=0;l<k;l++)
if(a[i][j][l]==0)
a[i][j][l]=5e8;
build();
while(o--){
cin>>p>>q;
r=get(p/k,q/k+1)[p%k][q%k];
if(r==5e8) r=-1;
cout<<r<<nl;
}
}
int main(){
L0TA;
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
17232 KB |
Output is correct |
2 |
Correct |
3 ms |
6748 KB |
Output is correct |
3 |
Correct |
1 ms |
6748 KB |
Output is correct |
4 |
Correct |
2 ms |
6748 KB |
Output is correct |
5 |
Correct |
4 ms |
6748 KB |
Output is correct |
6 |
Correct |
4 ms |
6808 KB |
Output is correct |
7 |
Correct |
4 ms |
6748 KB |
Output is correct |
8 |
Correct |
51 ms |
16988 KB |
Output is correct |
9 |
Correct |
51 ms |
16988 KB |
Output is correct |
10 |
Correct |
42 ms |
16220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
16720 KB |
Output is correct |
2 |
Correct |
2 ms |
6748 KB |
Output is correct |
3 |
Correct |
2 ms |
6748 KB |
Output is correct |
4 |
Correct |
1 ms |
6748 KB |
Output is correct |
5 |
Correct |
2 ms |
6748 KB |
Output is correct |
6 |
Correct |
1 ms |
6748 KB |
Output is correct |
7 |
Correct |
13 ms |
7004 KB |
Output is correct |
8 |
Correct |
15 ms |
7256 KB |
Output is correct |
9 |
Correct |
39 ms |
16988 KB |
Output is correct |
10 |
Correct |
68 ms |
14708 KB |
Output is correct |
11 |
Correct |
50 ms |
16836 KB |
Output is correct |
12 |
Correct |
55 ms |
13652 KB |
Output is correct |
13 |
Correct |
57 ms |
12376 KB |
Output is correct |
14 |
Correct |
31 ms |
11612 KB |
Output is correct |
15 |
Correct |
45 ms |
11348 KB |
Output is correct |
16 |
Correct |
45 ms |
11356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6748 KB |
Output is correct |
2 |
Correct |
2 ms |
6576 KB |
Output is correct |
3 |
Correct |
2 ms |
6744 KB |
Output is correct |
4 |
Correct |
1 ms |
6748 KB |
Output is correct |
5 |
Correct |
1 ms |
6748 KB |
Output is correct |
6 |
Correct |
2 ms |
6744 KB |
Output is correct |
7 |
Correct |
2 ms |
6748 KB |
Output is correct |
8 |
Correct |
3 ms |
6748 KB |
Output is correct |
9 |
Correct |
3 ms |
6792 KB |
Output is correct |
10 |
Correct |
26 ms |
17168 KB |
Output is correct |
11 |
Correct |
27 ms |
16476 KB |
Output is correct |
12 |
Correct |
40 ms |
14464 KB |
Output is correct |
13 |
Correct |
37 ms |
14836 KB |
Output is correct |
14 |
Correct |
30 ms |
14160 KB |
Output is correct |
15 |
Correct |
26 ms |
11092 KB |
Output is correct |
16 |
Correct |
26 ms |
11240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6748 KB |
Output is correct |
2 |
Correct |
2 ms |
6576 KB |
Output is correct |
3 |
Correct |
2 ms |
6744 KB |
Output is correct |
4 |
Correct |
1 ms |
6748 KB |
Output is correct |
5 |
Correct |
1 ms |
6748 KB |
Output is correct |
6 |
Correct |
2 ms |
6744 KB |
Output is correct |
7 |
Correct |
2 ms |
6748 KB |
Output is correct |
8 |
Correct |
3 ms |
6748 KB |
Output is correct |
9 |
Correct |
3 ms |
6792 KB |
Output is correct |
10 |
Correct |
26 ms |
17168 KB |
Output is correct |
11 |
Correct |
27 ms |
16476 KB |
Output is correct |
12 |
Correct |
40 ms |
14464 KB |
Output is correct |
13 |
Correct |
37 ms |
14836 KB |
Output is correct |
14 |
Correct |
30 ms |
14160 KB |
Output is correct |
15 |
Correct |
26 ms |
11092 KB |
Output is correct |
16 |
Correct |
26 ms |
11240 KB |
Output is correct |
17 |
Correct |
41 ms |
16464 KB |
Output is correct |
18 |
Correct |
2 ms |
6744 KB |
Output is correct |
19 |
Correct |
2 ms |
6748 KB |
Output is correct |
20 |
Correct |
2 ms |
6744 KB |
Output is correct |
21 |
Correct |
2 ms |
6748 KB |
Output is correct |
22 |
Correct |
2 ms |
6748 KB |
Output is correct |
23 |
Correct |
7 ms |
6968 KB |
Output is correct |
24 |
Correct |
9 ms |
7000 KB |
Output is correct |
25 |
Correct |
22 ms |
7008 KB |
Output is correct |
26 |
Correct |
16 ms |
6804 KB |
Output is correct |
27 |
Correct |
31 ms |
16988 KB |
Output is correct |
28 |
Correct |
51 ms |
14724 KB |
Output is correct |
29 |
Correct |
56 ms |
14924 KB |
Output is correct |
30 |
Correct |
48 ms |
14164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
17232 KB |
Output is correct |
2 |
Correct |
3 ms |
6748 KB |
Output is correct |
3 |
Correct |
1 ms |
6748 KB |
Output is correct |
4 |
Correct |
2 ms |
6748 KB |
Output is correct |
5 |
Correct |
4 ms |
6748 KB |
Output is correct |
6 |
Correct |
4 ms |
6808 KB |
Output is correct |
7 |
Correct |
4 ms |
6748 KB |
Output is correct |
8 |
Correct |
51 ms |
16988 KB |
Output is correct |
9 |
Correct |
51 ms |
16988 KB |
Output is correct |
10 |
Correct |
42 ms |
16220 KB |
Output is correct |
11 |
Correct |
51 ms |
16720 KB |
Output is correct |
12 |
Correct |
2 ms |
6748 KB |
Output is correct |
13 |
Correct |
2 ms |
6748 KB |
Output is correct |
14 |
Correct |
1 ms |
6748 KB |
Output is correct |
15 |
Correct |
2 ms |
6748 KB |
Output is correct |
16 |
Correct |
1 ms |
6748 KB |
Output is correct |
17 |
Correct |
13 ms |
7004 KB |
Output is correct |
18 |
Correct |
15 ms |
7256 KB |
Output is correct |
19 |
Correct |
39 ms |
16988 KB |
Output is correct |
20 |
Correct |
68 ms |
14708 KB |
Output is correct |
21 |
Correct |
50 ms |
16836 KB |
Output is correct |
22 |
Correct |
55 ms |
13652 KB |
Output is correct |
23 |
Correct |
57 ms |
12376 KB |
Output is correct |
24 |
Correct |
31 ms |
11612 KB |
Output is correct |
25 |
Correct |
45 ms |
11348 KB |
Output is correct |
26 |
Correct |
45 ms |
11356 KB |
Output is correct |
27 |
Correct |
1 ms |
6748 KB |
Output is correct |
28 |
Correct |
2 ms |
6576 KB |
Output is correct |
29 |
Correct |
2 ms |
6744 KB |
Output is correct |
30 |
Correct |
1 ms |
6748 KB |
Output is correct |
31 |
Correct |
1 ms |
6748 KB |
Output is correct |
32 |
Correct |
2 ms |
6744 KB |
Output is correct |
33 |
Correct |
2 ms |
6748 KB |
Output is correct |
34 |
Correct |
3 ms |
6748 KB |
Output is correct |
35 |
Correct |
3 ms |
6792 KB |
Output is correct |
36 |
Correct |
26 ms |
17168 KB |
Output is correct |
37 |
Correct |
27 ms |
16476 KB |
Output is correct |
38 |
Correct |
40 ms |
14464 KB |
Output is correct |
39 |
Correct |
37 ms |
14836 KB |
Output is correct |
40 |
Correct |
30 ms |
14160 KB |
Output is correct |
41 |
Correct |
26 ms |
11092 KB |
Output is correct |
42 |
Correct |
26 ms |
11240 KB |
Output is correct |
43 |
Correct |
41 ms |
16464 KB |
Output is correct |
44 |
Correct |
2 ms |
6744 KB |
Output is correct |
45 |
Correct |
2 ms |
6748 KB |
Output is correct |
46 |
Correct |
2 ms |
6744 KB |
Output is correct |
47 |
Correct |
2 ms |
6748 KB |
Output is correct |
48 |
Correct |
2 ms |
6748 KB |
Output is correct |
49 |
Correct |
7 ms |
6968 KB |
Output is correct |
50 |
Correct |
9 ms |
7000 KB |
Output is correct |
51 |
Correct |
22 ms |
7008 KB |
Output is correct |
52 |
Correct |
16 ms |
6804 KB |
Output is correct |
53 |
Correct |
31 ms |
16988 KB |
Output is correct |
54 |
Correct |
51 ms |
14724 KB |
Output is correct |
55 |
Correct |
56 ms |
14924 KB |
Output is correct |
56 |
Correct |
48 ms |
14164 KB |
Output is correct |
57 |
Correct |
134 ms |
15856 KB |
Output is correct |
58 |
Correct |
50 ms |
17228 KB |
Output is correct |
59 |
Correct |
70 ms |
16688 KB |
Output is correct |