Submission #1172297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172297		DanielPr8	Toll (BOI17_toll)	C++20	100 / 100	143 ms	74308 KiB

toll

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
#define f fisrt
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()

int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);
    ll k, n, m, o, f=20, a, b, t;
    cin >> k >> n >> m >> o;
    n+=k-n%k;
    vector<vvl> ed(f, vvl(n, vll(k, 1e11)));
    for(ll i = 0; i < m; ++i){
        cin >> a >> b >> t;
        ed[0][a][b%k]=t;
    }
    for(ll h = 1; h < f; ++h){
        for(ll i = 0; i < n; ++i){
            for(ll j = 0; j < k; ++j){
                for(ll p = 0; p < k; ++p){
                    ll l = i-i%k+(1<<(h-1))*k+p;
                    if(l<n)ed[h][i][j] = min(ed[h][i][j], ed[h-1][i][p] + ed[h-1][l][j]);
                }
            }
        }
    }
    while(o--){
        vll dis(k, 1e11), dis2;
        cin >> a >> b;
        t = b/k-a/k;
        dis[a%k]=0;
        a-=a%k;
        for(ll h = f-1; h >= 0; --h){
            if((1<<h)<=t){
                dis2 = vll(k, 1e11);
                for(ll i = 0; i < k; ++i){
                    for(ll j = 0; j < k; ++j){
                        dis2[i] = min(dis2[i],dis[j]+ed[h][a+j][i]);
                    }
                }
                t-=(1<<h);
                a+=(1<<h)*k;
                swap(dis, dis2);
            }
        }
        if(dis[b%k]<1e11)cout << dis[b%k] << "\n";
        else cout << "-1\n";
    }
}

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