Submission #380415

#	Time	Username	Problem	Language	Result	Execution time	Memory
380415		rqi	Toll (BOI17_toll)	C++14	100 / 100	687 ms	54240 KiB

toll

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

typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;

#define mp make_pair
#define pb push_back
#define f first
#define s second

#define sz(x) (int)(x).size()

void ckmin(int& a, int b){
    a = min(a, b);
}

const int MOD = 1e9+7;

const int mx = 50005;

int K, N, M, O;

vpi adj[mx];
vpi radj[mx];

pair<vi, vi> mid_dists[1<<17][5];

void genDists(int L, int R, int ind = 1){
    if(L > R) return;
    int M = (L+R)/2;

    //cout << "L, M, R: " << L << ", " << M << ", " << R << "\n";

    for(int rem = 0; rem < K; rem++){ //gen distances from M*K+rem
        //cout << "rem: " << rem << "\n";

        {
        
        mid_dists[ind][rem].f = vi((M-L+1)*K, MOD);
        vi& v = mid_dists[ind][rem].f;
        priority_queue<pi, vector<pi>, greater<pi>> pq;
        v[M*K+rem-L*K] = 0;
        pq.push(mp(v[M*K+rem-L*K], M*K+rem));
        while(sz(pq)){
            int node = pq.top().s; pq.pop();
            for(auto u: radj[node]){
                if(u.f < L*K) continue;
                if(v[u.f-L*K] <= v[node-L*K]+u.s){
                    continue;
                }
                v[u.f-L*K] = v[node-L*K]+u.s;
                pq.push(mp(v[u.f-L*K], u.f));
            }
        }

        }

        {

        mid_dists[ind][rem].s = vi((R-M+1)*K, MOD);
        vi& v = mid_dists[ind][rem].s;
        priority_queue<pi, vector<pi>, greater<pi>> pq;
        v[M*K+rem-M*K] = 0;
        pq.push(mp(v[M*K+rem-M*K], M*K+rem));
        while(sz(pq)){
            int node = pq.top().s; pq.pop();
            for(auto u: adj[node]){
                if(u.f >= (R+1)*K) continue;
                if(v[u.f-M*K] <= v[node-M*K]+u.s){
                    continue;
                }
                v[u.f-M*K] = v[node-M*K]+u.s;
                pq.push(mp(v[u.f-M*K], u.f));
            }
        }

        }

        // cout << "mid_dists[ind][rem].f:" << "\n";
        // for(int i = 0; i < sz(mid_dists[ind][rem].f); i++){
        //     cout << i << " " << mid_dists[ind][rem].f[i] << "\n";
        // }
        // cout << "mid_dists[ind][rem].s:" << "\n";
        // for(int i = 0; i < sz(mid_dists[ind][rem].s); i++){
        //     cout << i << " " << mid_dists[ind][rem].s[i] << "\n";
        // }
    }

    genDists(L, M-1, 2*ind);
    genDists(M+1, R, 2*ind+1);
}

int getDist(int a, int b, int L, int R, int ind = 1){
    int M = (L+R)/2;

    if(b/K < M){
        return getDist(a, b, L, M-1, 2*ind);
    }
    else if(M < a/K){
        return getDist(a, b, M+1, R, 2*ind+1);
    }

    int res = MOD;
    for(int rem = 0; rem < K; rem++){
        ckmin(res, mid_dists[ind][rem].f[a-L*K]+mid_dists[ind][rem].s[b-M*K]);
    }
    return res;
}

int main(){
    cin >> K >> N >> M >> O;
    for(int i = 1; i <= M; i++){
        int a, b, t;
        cin >> a >> b >> t;
        adj[a].pb(mp(b, t));
        radj[b].pb(mp(a, t));
    }
    genDists(0/K, (N-1)/K);

    for(int i = 1; i <= O; i++){
        int a, b;
        cin >> a >> b;
        int ans = getDist(a, b, 0/K, (N-1)/K);
        if(ans >= MOD) ans = -1;
        cout << ans << "\n";
    }
}

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