제출 #1268866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268866		Davdav1232	Toll (BOI17_toll)	C++20	100 / 100	197 ms	73544 KiB

toll

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> vii;
typedef long long ll;
int INF=1e9;

int main() {
    int K, N, M, O;
    cin>>K>>N>>M>>O;
    if(M==0){
        for(int i=0; i<O; i++){
            int a, b;
            cin>>a>>b;
            if(a==b) cout<<0<<"\n";
            else cout<<-1<<"\n";
        }
        return 0;
    }
    while(N%K!=0) N++;
    int T=N/K;

    vector<vector<vvi>> tolls(log2(T-1)+1, vector<vvi>(T-1, vvi(K, vi(K, 1e9+1))));
    for(int i=0; i<M; i++){
        int a, b, t;
        cin>>a>>b>>t;
        tolls[0][a/K][a%K][b%K]=t;
    }
    for(int i=1; (1<<i) <= T-1; i++){
        for(int j=0; j+(1<<i)<T; j++){
            for(int k=0; k<K; k++){
                for(int l=0; l<K; l++){
                    for(int m=0; m<K; m++){
                        tolls[i][j][k][l]=min(tolls[i-1][j][k][m]+tolls[i-1][j+(1<<(i-1))][m][l], tolls[i][j][k][l]);
                    }
                }
            }
        }
    }
    for(int i=0; i<O; i++){
        int a, b;
        cin>>a>>b;
        int c=a/K;
        int d=b/K;
        if(c==d){ 
            cout<<-1<<"\n";
            continue;
        }
        int q=0;
        vector<int> dp(K, 1e9+1);
        dp[a%K]=0;
        int e=d-c;
        while(e>0){
            vector<int> dp2(K, 1e9+1);
            if(e%2==0){
                q++;
                e/=2;
                continue;
            }
            for(int j=0; j<K; j++){
                for(int k=0; k<K; k++){
                    dp2[j]=min(dp2[j], dp[k]+tolls[q][c][k][j]);
                }
            }
            c+=(1<<q);
            q++;
            e/=2;
            dp=dp2;
        }
        if(dp[b%K]>1e9) cout<<-1<<"\n";
        else cout<<dp[b%K]<<"\n";
    }
    return 0;
}

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