Submission #1193137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193137		Newtonabc	Toll (BOI17_toll)	C++20	100 / 100	96 ms	98376 KiB

toll

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
//dp[i][j][k][l]=minimum distance from layer i node k to layer i+2^j node l
int dp[N][20][5][5];
void pt(int a,int b){
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            if(dp[a][b][i][j]!=INT_MAX) cout<<dp[a][b][i][j] <<" ";
            else cout<<"-" <<" ";
        }
        cout<<"\n";
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int k,n,m,q;
    cin>>k >>n >>m >>q;
    for(int i=0;i<=n;i++) for(int j=0;j<20;j++) for(int x=0;x<5;x++) for(int y=0;y<5;y++) dp[i][j][x][y]=INT_MAX;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a >>b >>c;
        int u=a/k,ul=a%k,vl=b%k;
        //cout<<u <<" " <<ul <<" " <<vl <<" " <<c <<"\n";
        dp[u][0][ul][vl]=c;
    }
    for(int i=1;i<20;i++){
        //for loop j until j+2^i exceed the number of layer
        for(int j=0;j+(1<<i)<=(n+k-1)/k;j++){
            //traverse from layer j to j+2^i
            for(int u=0;u<k;u++){
                for(int v=0;v<k;v++){
                    for(int m=0;m<k;m++){
                        int tmpa=dp[j][i-1][u][m];
                        int tmpb=dp[j+(1<<(i-1))][i-1][m][v];
                        if(tmpa!=INT_MAX && tmpb!=INT_MAX) dp[j][i][u][v]=min(dp[j][i][u][v],tmpa+tmpb);
                    }
                }
            }
        }
    }
    //pt(0,1);
    while(q--){
        int a,b;
        cin>>a >>b;
        int u=a/k,ul=a%k,v=b/k,vl=b%k;
        int now[5],prev[5];
        for(int i=0;i<k;i++) prev[i]=now[i]=INT_MAX;
        prev[ul]=0;
        for(int i=19;i>=0;i--){
            if(u+(1<<i)>v) continue;
            //cout<<i <<" ";
            //jump from u to u+(1<<i)
            for(int x=0;x<k;x++) now[x]=INT_MAX;
            for(int x=0;x<k;x++){
                for(int y=0;y<k;y++){
                    if(prev[x]!=INT_MAX && dp[u][i][x][y]!=INT_MAX) now[y]=min(now[y],prev[x]+dp[u][i][x][y]);
                }
            }
            for(int x=0;x<k;x++) prev[x]=now[x];
            u+=(1<<i);
        }
        if(now[vl]==INT_MAX) cout<<-1 <<"\n";
        else cout<<now[vl] <<"\n";
    }
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44