Submission #1285270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285270		surya999	Toll (BOI17_toll)	C++20	0 / 100	3094 ms	9028 KiB

toll

#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define inf 1e18
#define int long long 

struct q{
    int a , b , idx ;
};

const int N = 50005 ;

int k , n , m , o ;
vector <array <int , 2> > adj[N] ;
vector <array <int , 2> > radj[N] ;
int dis[N] , rdis[N] , ans[10004] ;
vector <q> qu ;
priority_queue <array <int , 2> > pq ;

void cal(int node) {

    for(int i = 0 ; i < n ; i ++) dis[i] = rdis[i] = inf ;
    dis[node] = 0 ;
    pq.push({0 , node}) ;
    

    while(!pq.empty()) {
        auto v = pq.top() ;
        pq.pop() ;
        int cd = -v[0] ;
        int node = v[1] ;
        if(cd != dis[node]) continue ;
        for(auto &nxt : adj[node]) {
            int w = nxt[1] ;
            int to = nxt[0] ;
            if(cd + w < dis[to]) {
                dis[to] = cd + w ;
                pq.push({-dis[to] , to}) ;
            }
        }
    }

    rdis[node] = 0 ;
    pq.push({0 , node}) ;

    while(!pq.empty()) {
        auto v = pq.top() ;
        pq.pop() ;
        int cd = -v[0] ;
        int node = v[1] ;
        if(cd != rdis[node]) continue ;
        for(auto &nxt : radj[node]) {
            int w = nxt[1] ;
            int to = nxt[0] ;
            if(cd + w < rdis[to]) {
                rdis[to] = cd + w ;
                pq.push({-rdis[to] , to}) ;
            }
        }
    }

}


void f(int l , int r , vector <q> &qu) {
    if(l > r) return ;
    int mid = (l + r) / 2 ;
    vector <q> lf , rf ;

    // mid , mid + 1 , mid + k - 1 
    for(int i = mid * k ; i <= mid * k + k - 1 ; i ++) {
        cal(i) ;
        for(auto &q : qu) {
            ans[q.idx] = min(ans[q.idx] , rdis[q.a] + dis[q.b]) ;
        }
    }
    for(auto &q : qu) {
        
        if(q.a < mid * k && q.b < mid * k) lf.push_back(q) ;
        if(q.a > mid * k + k - 1 && q.b > mid * k + k - 1) rf.push_back(q) ;
    }
    if(l < mid) f(l , mid , lf) ;
    if(mid + 1 <= r) f(mid + 1 , r , rf) ;

}







void solve() {
       
    cin >> k >> n >> m >> o ;
    while(n % k != (k - 1)) n ++ ;
    for(int i = 0 ; i < m ; i ++) {
        int u , to , w ;
        cin >> u >> to >> w ;
        adj[u].push_back({to , w}) ;
        radj[to].push_back({u , w}) ;
    }

    for(int i = 0 ; i < o ; i ++) {
        int a , b ;
        cin >> a >> b ;
        qu.push_back({a , b , i}) ;
        ans[i] = inf ;
    }
    f(0 , n / k , qu) ;
    for(int i = 0 ; i < o ; i ++) cout << (ans[i] == inf ? -1 : ans[i]) << " " ;
    cout << endl ;
}










int32_t main() {
    fastio();
  
    
    int testcase = 1;
    //cin >> testcase;
    
    for(int t = 1 ; t <= testcase ; t ++) {
     // cout << "Case #" << t << ": " ;
      solve() ;
    }
    return 0;
}

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