Submission #1123193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123193		asli_bg	Toll (BOI17_toll)	C++20	100 / 100	307 ms	12916 KiB

toll

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

#define int long long

#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sp <<' '<<
#define pb push_back

#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)

#define cont(a) for(auto el:a) cout<<el<<' '; cout<<endl;
#define contp(a) for(auto el:a) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;

#define DEBUG(x) cout<<#x sp ":" sp x<<endl;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef long long ll;

#define topla(x,y) ((x%MOD)+(y%MOD))%MOD
#define carp(x,y) ((x%MOD)*(y%+MOD))%MOD

const int MAXN=5e4+5;
const int INF=1e18;

#define mid ((l+r)/2)

int n,m,k,o;
vii adj[MAXN], revadj[MAXN];
int cev[MAXN], bb[MAXN], dist[MAXN];

void dij(int bas,int l,int r){
    priority_queue<pii,vii,greater<pii>> pq;

    FOR(i,n) dist[i]=INF;
    dist[bas]=0;

    pq.push({0,bas});

    while(!pq.empty()){
        auto el=pq.top();
        pq.pop();

        int d=el.fi;
        int nd=el.se;

        for(auto [kom,cost]:adj[nd]){
            if(bb[kom]<l or bb[kom]>r) continue;
            if(dist[nd]+cost<dist[kom]){
                dist[kom]=dist[nd]+cost;
                pq.push({dist[kom],kom});
            }
        }
    }

    pq.push({0,bas});

    while(!pq.empty()){
        auto el=pq.top();
        pq.pop();

        int d=el.fi;
        int nd=el.se;

        for(auto [kom,cost]:revadj[nd]){
            if(bb[kom]<l or bb[kom]>r) continue;

            if(dist[nd]+cost<dist[kom]){
                dist[kom]=dist[nd]+cost;
                pq.push({dist[kom],kom});
            }

        }
    }
}

void solve(int l,int r,vector<pair<pii,int>>& qq){
    if(l>r or qq.empty()) return;

    for(int i=mid*k;i<min(mid*k+k,n);i++){
        dij(i,l,r);
        for(auto el:qq){
            int bas=el.fi.fi;
            int son=el.fi.se;
            int ind=el.se;

            if(bb[bas]<=mid and mid<=bb[son]) cev[ind]=min(cev[ind],dist[bas]+dist[son]);
        }
    }

    vector<pair<pii,int>> sag,sol;
    for(auto el:qq){
        if(bb[el.fi.se]<mid) sol.pb(el);
        if(bb[el.fi.fi]>mid) sag.pb(el);
    }

    solve(l,mid,sol);
    solve(mid+1,r,sag);
}


signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>k>>n>>m>>o;
    FOR(i,m){
        int a,b,t;
        cin>>a>>b>>t;
        adj[a].pb({b,t});
        revadj[b].pb({a,t});
    }

    FOR(i,n) bb[i]=i/k;
    FORE(i,1,o+1) cev[i]=INF; 

    vector<pair<pii,int>> qq;
    int say=1;
    while(o--){
        int a,b;
        cin>>a>>b;
        qq.pb({{a,b},say++});
    }

    solve(0,bb[n-1],qq);
    FORE(i,1,say) cout<<(cev[i]==INF?-1:cev[i])<<endl;
}

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