Submission #1307186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307186		goppamach	Toll (BOI17_toll)	C++20	100 / 100	757 ms	149720 KiB

toll

// #pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

#define el "\n"
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define mp make_pair
#define sqr(x) ((x) * (x))
#define FOR(i, l, r) for (int i = l; i <= (r); i++)
#define FOD(i, l, r) for (int i = l; i >= (r); i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) ((int)(x).size())
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr);

using db = long double;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using vvi = vector<vi>;
using vvll = vector<vll>;
using vbool = vector<bool>;
using vvbool = vector<vbool>;

template<class T> inline bool chmax(T &a, T const &b) { return (a < b ? (a = b, true) : false); }
template<class T> inline bool chmin(T &a, T const &b) { return (a > b ? (a = b, true) : false); }

// #define DEBUG
#ifdef DEBUG
#include "D:\cpp\debug.h"
#else
#define debug(...)
#define debug_arr(...)
#endif

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

constexpr int N = 5E4 + 5, Q = 1E4 + 5;
constexpr int INF = 1E9 + 7;
constexpr ll INFLL = 4E18;
constexpr int MOD = 1E9 + 7; // 998244353
constexpr double EPS = 1E-10;

struct Query {
    int a, b, id;

    Query(int a, int b, int id): a(a), b(b), id(id) {}
};

vpii adj[N], rev[N];
ll res[Q];
unordered_map<int, unordered_map<int, ll>> d[2];
int k, n, m, q;

void dijkstra(int s, int l, int r, unordered_map<int, ll> &d, vpii adj[]) {
    int block_l = l / k, block_r = r / k;
    FOR(i, block_l * k, min(n - 1, (block_r + 1) * k - 1)) {
        d[i] = INFLL;
    }
    priority_queue<pll, vpll, greater<pll>> pq;
    pq.emplace(0, s);
    d[s] = 0;

    while (!pq.empty()) {
        auto [dist, u] = pq.top();
        pq.pop();
        if (dist != d[u]) continue;
        for (auto &[v, t] : adj[u]) {
            if (v / k < block_l || v / k > block_r) continue;
            if (chmin(d[v], d[u] + t)) {
                pq.emplace(d[v], v);
            }
        }
    }
}

void dnc(int l, int r, vector<Query> &queries) {
    if (l / k >= r / k) return;
    int m = (l + r) / 2;
    int block_m = m / k;
    FOR(i, 0, k - 1) {
        int x = block_m * k + i;
        dijkstra(x, l, m, d[0][x], rev);
        dijkstra(x, m, r, d[1][x], adj);
    }

    vector<Query> todo[2];
    for (auto &[l, r, id] : queries) {
        if (l <= m && m < r) {
            FOR(i, 0, k - 1) {
                int x = block_m * k + i;
                chmin(res[id], d[0][x][l] + d[1][x][r]);
            }
        } else {
            todo[l > m].emplace_back(l, r, id);
        }
    }

    dnc(l, m, todo[0]);
    dnc(m + 1, r, todo[1]);
}

void solve() {
    cin >> k >> n >> m >> q;

    while (m--) {
        int a, b, t;
        cin >> a >> b >> t;
        // floor(a / k) + 1 = floor(b / k)
        adj[a].emplace_back(b, t);
        rev[b].emplace_back(a, t);
    }

    vector<Query> queries;
    FOR(i, 1, q) {
        int a, b;
        cin >> a >> b;
        queries.emplace_back(a, b, i);
    }

    fill(all(res), INFLL);
    dnc(0, n - 1, queries);
    FOR(i, 1, q) {
        cout << (res[i] == INFLL ? -1 : res[i]) << el;
    }
}

int main() {
    fast_io
    #define LOCAL
    #ifndef LOCAL
    #define PROBLEM ""
    freopen(PROBLEM ".INP", "r", stdin);
    freopen(PROBLEM ".OUT", "w", stdout);
    #endif

    int t = 1;
    // cin >> t;
    while (t--) solve();
}

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