Submission #1129939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129939		vladilius	Toll (BOI17_toll)	C++20	0 / 100	47 ms	7040 KiB

toll

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int inf = 1e9;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int k, n, m, q; cin>>k>>n>>m>>q;
    vector<pii> g1[n + 1], g2[n + 1];
    while (m--){
        int x, y, t; cin>>x>>y>>t;
        x++; y++;
        g1[x].pb({y, t});
        g2[y].pb({x, t});
    }
    
    vector<int> f(n + 1);
    for (int i = 1; i <= n; i++){
        f[i] = (i - 1) / k + 1;
    }
    
    vector<int> x(q + 1), y(q + 1), qs;
    for (int i = 1; i <= q; i++){
        cin>>x[i]>>y[i];
        x[i]++; y[i]++;
        if (x[i] >= y[i]) continue;
        qs.pb(i);
    }
    
    vector<int> out(q + 1, inf);
    vector<vector<int>> dist(k + 1, vector<int>(n + 1));
    function<void(int, int, vector<int>)> solve = [&](int l, int r, vector<int> qq){
        if (l == r) return;
        int m = (l + r) / 2;
        vector<int> left, right, cur;
        for (int i: qq){
            if (f[y[i]] <= m){
                left.pb(i);
                continue;
            }
            if (f[x[i]] > m){
                right.pb(i);
                continue;
            }
            cur.pb(i);
        }
        
        for (int j = 1; j <= k; j++){
            for (int i = (l - 1) * k + 1; i <= min(n, r * k - 1); i++){
                dist[j][i] = inf;
            }
            dist[j][(m - 1) * k + j] = 0;
            for (int i = (m - 1) * k + j; i <= min(n, r * k - 1); i++){
                for (auto [v, t]: g1[i]){
                    dist[j][v] = min(dist[j][v], dist[j][i] + t);
                }
            }
            for (int i = (m - 1) * k + j; i >= (l - 1) * k + 1; i--){
                for (auto [v, t]: g2[i]){
                    dist[j][v] = min(dist[j][v], dist[j][i] + t);
                }
            }
        }
        
        for (int i: cur){
            for (int j = 1; j <= k; j++){
                out[i] = min(out[i], dist[j][x[i]] + dist[j][y[i]]);
            }
        }
        
        
        solve(l, m, left);
        solve(m + 1, r, right);
    };
    solve(f[1], f[n], qs);
    
    for (int i = 1; i <= q; i++){
        cout<<((out[i] == inf) ? -1 : out[i])<<"\n";
    }
}

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