Submission #399545

#	Time	Username	Problem	Language	Result	Execution time	Memory
399545		Andyvanh1	Toll (BOI17_toll)	C++14	7 / 100	249 ms	54908 KiB

toll

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;



#define vt vector
#define pb push_back

typedef long long ll;
typedef vt<int> vi;


#define INF 2000000000

int N,M,K;

vt<vt<vt<vi>>> dp;

vt<vi> arr;
vt<vt<pair<int,int>>> adjlist;

void gen(){
    for(int f = 1; f < 17; f++){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < K; j++){
                for(int l = 0; l < K; l++ ){
                    if(i+(1<<(f-1))<N) {
                        for(int a = 0; a < K; a++){
                            dp[i][j][f][l] = min(dp[i][j][f][l],dp[i][j][f - 1][a] + dp[i + (1 << (f - 1))][a][f - 1][l]);
                        }

                    }
                }
            }
        }
    }

}

int get(int i, int j, int f, int l){
    vi cur(K);
    f--;
    for(int a = 0; a < K; a++){
        cur[a] = dp[i][j][0][a];
    }
    i++;

    for(int a = 0; a < 17; a++){

        if((1<<a)&f){
            vi part(K);
            for(int b = 0; b < K; b++){
                part[b] = INF/3;
            }
            for(int b = 0; b < K; b++){
                for(int c = 0; c < K; c++){
                    if(dp[i][c][a][b]!=INF/3){
                        part[b] = min(part[b],cur[c]+dp[i][c][a][b]);
                    }
                }
            }
            i+=(1<<a);
            for(int b = 0; b < K; b++){
                cur[b] = part[b];
            }

        }

    }
    if(cur[l]==INF/3){
        return -1;
    }
    return cur[l];

}

void solve(){
    int  m, n, o;
    cin>>K>>n>>m>>o;
    N = (n-1)/K+1;
    arr.resize(N,vi(K));
    adjlist.resize(n);
    dp.resize(N,vt<vt<vi>>(K,vt<vi>(17,vi(K))));

    for(int i = 0; i < N; i++){
        for(int j = 0; j < K; j++){
            for(int l = 0; l < K; l++){
                for(int f = 0; f < 17; f++) {
                    dp[i][j][f][l] = INF / 3;
                }
            }
        }
    }


    for(int i = 0; i < m; i++){
        int u,v,w;
        cin>>u>>v>>w;
        dp[u/K][u%K][0][v%K] = w;
    }

    gen();

    for(int i = 0; i < o; i++){
        int u,v;
        cin>>u>>v;
        cout<<get(u/K,u%K,(v/K-u/K),v%K)<<'\n';
    }

}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    //cin>>t;
    for(int i = 0; i < t; i++){
        solve();
    }
    return 0;
}

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