Submission #915806

#	Time	Username	Problem	Language	Result	Execution time	Memory
915806		asdasdqwer	Toll (BOI17_toll)	C++14	100 / 100	362 ms	69556 KiB

toll

#include <bits/stdc++.h>
using namespace std;

#define int int64_t
const int INF = 1e14;

signed main() {
    int k,n,m,o;cin>>k>>n>>m>>o;
    int cl=(n/k)+1;
    vector<vector<vector<vector<int>>>> lft(cl, vector<vector<vector<int>>>(k, vector<vector<int>>(18, vector<int>(k, INF))));

    for (int i=0;i<m;i++) {
        int a,b,t;cin>>a>>b>>t;
        lft[a/k][a%k][0][b%k]=t;
    }

    for (int j=1;j<18;j++) {
        for (int i=0;i<cl;i++) {
            if (i + (1<<j) >= cl)break;
            
            for (int t=0;t<k;t++) {
                for (int md=0;md<k;md++) {
                    for (int tr=0;tr<k;tr++) {
                        lft[i][t][j][tr] = min(lft[i][t][j][tr], lft[i][t][j-1][md] + lft[i+(1<<(j-1))][md][j-1][tr]);
                    }
                }
            }
        }
    }

    while (o--) {
        int a,b;cin>>a>>b;

        if ((a/k) == (b/k)) {
            cout<<"-1\n";
            continue;
        }

        int rw = a/k, co=a%k;
        int steps = (b/k) - (a/k);
        vector<int> jmp(k);
        for (int i=0;i<k;i++) {
            jmp[i] = lft[rw][co][0][i];
        }

        steps--;
        rw++;

        int cnt=0;
        while (steps) {
            if ((steps&1)==1) {
                vector<int> tmpjmp(k, INF);
                for (int i=0;i<k;i++) {
                    // use i as a starting point

                    for (int j=0;j<k;j++) {
                        // use j as an ending point
                        tmpjmp[j] = min(tmpjmp[j], jmp[i] + lft[rw][i][cnt][j]);
                    }
                }

                jmp = tmpjmp;
                rw+=(1<<cnt);
            }

            steps>>=1;
            cnt++;
        }

        if (jmp[b%k] >= INF) {
            cout<<-1<<"\n";
            continue;
        }

        cout<<jmp[b%k]<<"\n";
    }
}

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