Submission #1123188

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123188		asli_bg	Toll (BOI17_toll)	C++20	100 / 100	260 ms	12932 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 mid (l+r)/2

#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;;

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

void dij(int bas,int l,int r){
    //bas bloğundan itibaren [l-r] aralığına shortest path at
    FOR(i,n) dist[i]=INF;

    priority_queue<pii, vii, greater<pii>> q;
    q.push({0,bas});

    dist[bas]=0;

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

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

        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;
                q.push({dist[kom],kom});
            }

        }
    }

    q.push({0,bas});

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

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

        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;
                q.push({dist[kom],kom});
            }

        }
    }
}


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

    int mid=(a+b)/2; //ikisinin de geçmek zorunda olduğu blok

    //i'nin bloğu--> i/k
    //i'nin bloğundaki elemanlar --> [i*k,i*(k+1)-1];


    for(int i=k*mid;i<min(n,k*mid+k);i++){ //bu bloktaki her elemandan shortest path at
        dij(i,a,b);
    
        for(auto el:qq){
            int bas=el.fi.fi;
            int son=el.fi.se;
            int ind=el.se;

            if(bb[bas]<=mid and bb[son]>=mid){
                //querynin ayrıldığı kısım
                cev[ind]=min(cev[ind],dist[bas]+dist[son]);
            }
        }
    }

    vector<pair<pii,int>> l,r;
    for(auto el:qq){ //queryler midin neresinde kalıyor
        if(bb[el.fi.se]<mid) l.pb(el);
        if(bb[el.fi.fi]>mid) r.pb(el);
    }

    solve(a,mid,l);
    solve(mid+1,b,r);
}

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;
    
    vector<pair<pii,int>> qq;

    FORE(i,1,o+1) cev[i]=INF;

    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