# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
630822 |
2022-08-17T07:14:12 Z |
bachhoangxuan |
Toll (BOI17_toll) |
C++17 |
|
87 ms |
22172 KB |
#include<bits/stdc++.h>
using namespace std;
#define maxn 50005
#define maxl 20
#define maxk 5
const int inf=1e9;
int dp[maxn][maxl][maxk],n,m,k,t,Min[maxk],nMin[maxk];
int query(int u,int v){
for(int i=0;i<k;i++) Min[i]=nMin[i]=inf;
Min[u%k]=0;
int ub=u/k,vb=v/k;
for(int i=15;i>=0;i--){
if((vb-ub)&(1<<i)){
for(int j=0;j<k;j++) nMin[j]=inf;
for(int p=0;p<k;p++){
for(int j=0;j<k;j++){
int cur=ub*k+p;
nMin[j]=min(nMin[j],Min[p]+dp[cur][i][j]);
}
}
ub+=(1<<i);
for(int j=0;j<k;j++) Min[j]=nMin[j];
}
}
return Min[v%k];
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin >> k >> n >> m >> t;
for(int u=1;u<=n;u++){
for(int i=0;i<=15;i++){
for(int j=0;j<k;j++) dp[u][i][j]=inf;
}
}
for(int i=1;i<=m;i++){
int u,v,w;cin >> u >> v >> w;
dp[u][0][v%k]=w;
}
for(int i=1;i<=15;i++){
for(int u=0;u<n;u++){
for(int j=0;j<k;j++){
dp[u][i][j]=inf;
for(int p=0;p<k;p++){
int nxt=((u/k)+(1<<(i-1)))*k+p;
if(nxt>=n) continue;
dp[u][i][j]=min(dp[u][i][j],dp[u][i-1][p]+dp[nxt][i-1][j]);
}
//if(dp[u][i][j]!=inf) cout << u << ' ' << i << ' ' << j << ' ' << dp[u][i][j] << '\n';
}
}
}
for(int i=1;i<=t;i++){
int u,v;cin >> u >> v;
int x=query(u,v);
if(x==inf) cout << -1 << '\n';
else cout << x << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
20772 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
328 KB |
Output is correct |
4 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
21544 KB |
Output is correct |
2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
328 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
752 KB |
Output is correct |
8 |
Correct |
2 ms |
664 KB |
Output is correct |
9 |
Correct |
2 ms |
776 KB |
Output is correct |
10 |
Correct |
44 ms |
20692 KB |
Output is correct |
11 |
Correct |
49 ms |
21296 KB |
Output is correct |
12 |
Correct |
70 ms |
22032 KB |
Output is correct |
13 |
Correct |
87 ms |
22172 KB |
Output is correct |
14 |
Correct |
67 ms |
21668 KB |
Output is correct |
15 |
Correct |
49 ms |
13140 KB |
Output is correct |
16 |
Correct |
48 ms |
13204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
328 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
752 KB |
Output is correct |
8 |
Correct |
2 ms |
664 KB |
Output is correct |
9 |
Correct |
2 ms |
776 KB |
Output is correct |
10 |
Correct |
44 ms |
20692 KB |
Output is correct |
11 |
Correct |
49 ms |
21296 KB |
Output is correct |
12 |
Correct |
70 ms |
22032 KB |
Output is correct |
13 |
Correct |
87 ms |
22172 KB |
Output is correct |
14 |
Correct |
67 ms |
21668 KB |
Output is correct |
15 |
Correct |
49 ms |
13140 KB |
Output is correct |
16 |
Correct |
48 ms |
13204 KB |
Output is correct |
17 |
Correct |
54 ms |
21408 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
20772 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
328 KB |
Output is correct |
4 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |