Submission #557576

#	Time	Username	Problem	Language	Result	Execution time	Memory
557576		fatemetmhr	Toll (BOI17_toll)	C++17	0 / 100	3062 ms	8600 KiB

toll

// `Be name khoda` //

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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


const int maxn5 = 1e5 + 10;
const int inf   = 1e9;

int ssq   = 2;
int h[maxn5], h2[maxn5], dis[2][maxn5][6];
int av[maxn5], av2[maxn5];
vector <pair<int, int>> jda[maxn5], adj[maxn5];
int k;

inline int get_dis(int a, int b){
    fill(h + a, h + b + 5, inf);
    h[b] = 0;
    for(int i = b; i > a; i--){
        for(auto [u, t] : jda[i])
            h[u] = min(h[u], h[i] + t);
    }
    return h[a];
}

inline void build(int id){
    for(int i = id; i < id + ssq; i++){
        fill(h + id, h + id + ssq + 3, inf);
        h[i] = 0;
        for(int j = i; j < id + ssq; j++) for(auto [u, t] : adj[j])
            h[u] = min(h[u], h[j] + t);
        for(int j = i; j >= id; j--) for(auto [u, t] : jda[j])
            h[u] = min(h[u], h[j] + t);
        for(int j = 0; j < k; j++){
            dis[0][i][j] = h[id + j];
            dis[1][i][j] = h[id + ssq - k + j];
        }
    }
    return;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n, m, q; cin >> k >> n >> m >> q;
    ssq *= k;
    for(int i = 0; i < m; i++){
        int a, b, t; cin >> a >> b >> t;
        jda[b].pb({a, t});
        adj[a].pb({b, t});
    }
    for(int i = 0; i < ssq; i++)
        build(i);
    for(int i = 0; i < q; i++){
        int a, b; cin >> a >> b;
        int cmpa = a / ssq * ssq;
        int cmpb = b / ssq * ssq;
        if(cmpa == cmpb){
            int ans = get_dis(a, b);
            if(ans == inf)
                ans = -1;
            cout << ans << '\n';
            continue;
        }
        for(int i = 0; i < k; i++){ // akhare cmpa
            av[i] = cmpa + ssq - k + i;
            h[i] = dis[1][a][i];
            h2[i] = inf;
        }
        for(int i = 0; i < k; i++) for(auto [u, t] : adj[av[i]])
            h2[u - cmpa - ssq] = min(h2[u - cmpa - ssq], h[i] + t);
        for(int i = 0; i < k; i++){ // avale cmpa + ssq
            av[i] = cmpa + ssq + i;
            h[i] = h2[i];
            h2[i] = inf;
        }
        cmpa += ssq;
        while(cmpa != cmpb){
            for(int i = 0; i < k; i++){ // avale cmpa
                av2[i] = cmpa + ssq - k + i;
                h2[i] = inf;
            }
            for(int i = 0; i < k; i++) for(int j = 0; j < k; j++)
                h2[j] = min(h2[j], dis[1][av[i]][j] + h[i]);
            for(int i = 0; i < k; i++){ // akhare cmpa
                av[i] = av2[i];
                h[i] = h2[i];
                h2[i] = inf;
            }
            for(int i = 0; i < k; i++) for(auto [u, t] : adj[av[i]])
                h2[u - cmpa - ssq] = min(h2[u - cmpa - ssq], h[i] + t);
            for(int i = 0; i < k; i++){ // avale cmpa + ssq
                av[i] = av2[i];
                h[i] = h2[i];
            }
            cmpa += ssq;
        }
        int ans = inf;
        for(int i = 0; i < k; i++)
            ans = min(ans, h[i] + dis[0][b][i]);
        if(ans == inf)
            ans = -1;
        cout << ans << '\n';
    }
}

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