Submission #1294455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294455		sunflower	Toll (BOI17_toll)	C++17	7 / 100	30 ms	9540 KiB

toll

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)

#define fi first
#define se second
#define left    __left
#define right   __right
#define prev    __prev
#define next    __next

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

const long long INF = (long long) 1e18 + 7;

struct Query {
    int u, v;
};

#define MAX_NODE 50500
#define MAX_QUERY 10100
int K, numNode, numEdge, numQuery;

vector<int> layer[MAX_NODE + 2];
vector<pair<int, int>> adj[MAX_NODE + 2], revAdj[MAX_NODE + 2];
Query query[MAX_QUERY + 2];
ll ans[MAX_QUERY + 2], minDist[MAX_NODE + 2];

void dnc(int l, int r, const vector<int> &que) {
    if (l == r) return;

    int g = (l + r) >> 1;
    vector<int> solveLeft, solveRight, solve;
    for (int id : que) {
        if (query[id].v / K <= g) solveLeft.push_back(id);
        else if (query[id].u / K > g) solveRight.push_back(id);
        else solve.push_back(id);
    }

    if (!solveLeft.empty()) dnc(l, g, solveLeft);
    if (!solveRight.empty()) dnc(g + 1, r, solveRight);

    if (solve.empty()) return;

    for (int nodes : layer[g]) {
        minDist[nodes] = 0;
        FORD(i, g - 1, l) {
            for (int u : layer[i]) {
                minDist[u] = INF;
                for (const pair<int, int> &e : adj[u]) {
                    int v = e.fi, w = e.se;
                    minimize(minDist[u], minDist[v] + w);
                }
            }
        }

        FOR(i, g + 1, r) {
            for (int u : layer[i]) {
                minDist[u] = INF;
                for (const pair<int, int> &e : revAdj[u]) {
                    int v = e.fi, w = e.se;
                    minimize(minDist[u], minDist[v] + w);
                }
            }
        }

        for (int id : solve) {
            int u = query[id].u, v = query[id].v;
            minimize(ans[id], minDist[u] + minDist[v]);
        }

        minDist[nodes] = INF;
    }

}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    cin >> K >> numNode >> numEdge >> numQuery;
    FOR(i, 1, numEdge) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(v, w));
        revAdj[v].push_back(make_pair(u, w));
    }

    /// toi da K diem in each layer;
    FOR(i, 0, numNode - 1) layer[i / K].push_back(i);

    vector<int> queries;
    FOR(i, 1, numQuery) {
        cin >> query[i].u >> query[i].v;
        if (query[i].u / K != query[i].v / K) queries.push_back(i);
    }

    FOR(i, 1, numQuery) ans[i] = INF;
    dnc(0, (numNode - 1) / K, queries);

    FOR(i, 1, numQuery) cout << (ans[i] != INF ? ans[i] : -1) << "\n";

    return 0;
}

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