oj.uz

Submission #630822

# Submission time Handle Problem Language Result Execution time Memory
630822 2022-08-17T07:14:12 Z bachhoangxuan Toll (BOI17_toll) C++17
8 / 100
 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';
    }
}

Subtask #1
0 / 7.0

# 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 -

Subtask #2
0 / 10.0

# 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 -

Subtask #3
8.0 / 8.0

# 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

Subtask #4
0 / 31.0

# 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 -

Subtask #5
0 / 44.0

# 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 -