Submission #1162745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162745		AlgorithmWarrior	Toll (BOI17_toll)	C++20	100 / 100	146 ms	18064 KiB

toll

#include <bits/stdc++.h>

using namespace std;

int const INF=1e9;
int const MAX=5e4+5;
int const LOG=18;
int k,n,m,q;
int dist[MAX][LOG][5];

void read(){
    cin>>k>>n>>m>>q;
    int i;
    for(i=1;i<=m;++i){
        int u,v,w;
        cin>>u>>v>>w;
        dist[u][0][v%k]=w;
    }
}

void minself(int& x,int val){
    if(x>val)
        x=val;
}

void precalc(){
    int i,j,rest,inter;
    for(i=0;i<n;++i)
        for(j=0;j<LOG;++j)
            for(rest=0;rest<k;++rest)
                if(!dist[i][j][rest])
                    dist[i][j][rest]=INF;
    for(j=1;j<LOG;++j)
        for(i=0;i<n;++i)
            for(rest=0;rest<k;++rest)
                for(inter=0;inter<k;++inter)
                    if(i/k*k+k*(1<<(j-1))+inter<n)
                        minself(dist[i][j][rest],dist[i][j-1][inter]+dist[i/k*k+k*(1<<(j-1))+inter][j-1][rest]);
}

int solve(int u,int v){
    int hu=u/k;
    int hv=v/k;
    int difh=hv-hu;
    vector<int>nodes(k);
    vector<int>dst(k);
    int i;
    for(i=0;i<k;++i){
        nodes[i]=u/k*k+i;
        if(u==nodes[i])
            dst[i]=0;
        else
            dst[i]=INF;
    }
    int bit;
    for(bit=0;(1<<bit)<=difh;++bit)
        if(difh&(1<<bit)){
            vector<int>new_nodes(k);
            vector<int>new_dst(k);
            int rest,inter;
            for(rest=0;rest<k;++rest){
                new_nodes[rest]=nodes[rest]+k*(1<<bit);
                new_dst[rest]=INF;
            }
            for(rest=0;rest<k;++rest)
                for(inter=0;inter<k;++inter)
                    minself(new_dst[rest],dst[inter]+dist[nodes[inter]][bit][rest]);
            for(rest=0;rest<k;++rest){
                nodes[rest]=new_nodes[rest];
                dst[rest]=new_dst[rest];
            }
        }
    if(dst[v%k]<INF)
        return dst[v%k];
    return -1;
}

void process_queries(){
    int i;
    for(i=1;i<=q;++i){
        int u,v;
        cin>>u>>v;
        cout<<solve(u,v)<<'\n';
    }
}

int main()
{
    read();
    precalc();
    process_queries();
    return 0;
}

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