Submission #1304069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304069		mocha	Toll (BOI17_toll)	C++20	100 / 100	367 ms	13248 KiB

toll

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mx = 5e4+5;
const int inf = 1e18;

int k, n, m, o;
vector<pair<int, int>> g[mx], rg[mx];
int dis[mx];

struct query {
    int id;
    int u, v;
};

int ans[mx];

void dij(int id, int l, int r) {
    for (int i=l;i<=r;i++) {
        dis[i] = inf;
    }
    dis[id] = 0;
    priority_queue<pair<int, int>> pq;
    pq.push({-dis[id], id});
    while (pq.size()) {
        auto [d, u] = pq.top(); pq.pop();
        d = -d;
        if (d > dis[u]) continue;
        for (auto [v, w]:g[u]) {
            if (v > r) continue;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                pq.push({-dis[v], v});
            }
        }
    }
    pq.push({-dis[id], id});
    while (pq.size()) {
        auto [d, u] = pq.top(); pq.pop();
        d = -d;
        if (d > dis[u]) continue;
        for (auto [v, w]:rg[u]) {
            if (v < l) continue;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                pq.push({-dis[v], v});
            }
        }
    }
}

void solve(int l, int r, vector<query> qs) {
    if (l >= r) return;
    int m = l + r >> 1;
    vector<query> ls, rs, its;
    for (auto [id, u, v]:qs) {
        if (v/k < m) ls.push_back({id, u, v});
        else if (m < u/k) rs.push_back({id, u, v});
        else its.push_back({id, u, v});
    }
    solve(l, m-1, ls);
    solve(m+1, r, rs);
    for (int i=0;i<k;i++) {
        dij(m*k+i, l*k, (r+1)*k-1);
        for (auto [id, u, v]:its) {
            ans[id] = min(ans[id], dis[u] + dis[v]);
        }
    }
}

signed main() {
    cin >> k >> n >> m >> o;
    for (int i=1;i<=m;i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        rg[v].push_back({u, w});
    }
    vector<query> qs;
    for (int i=1;i<=o;i++) {
        int u, v;
        cin >> u >> v;
        qs.push_back({i, u, v});
        ans[i] = inf;
    }
    solve(0, n/k, qs);
    for (int i=1;i<=o;i++) {
        if (ans[i] == inf) cout << -1 << "\n";
        else cout << ans[i] << "\n";
    }
}

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