Submission #536492

#	Time	Username	Problem	Language	Result	Execution time	Memory
536492		KiriLL1ca	Toll (BOI17_toll)	C++17	0 / 100	64 ms	18108 KiB

toll

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define endl '\n'
#define pb push_back
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pw(x) (1ll << x)

#pragma GCC optimize ("-O3")
#pragma GCC optimize ("unroll-loops")

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef long double ld;

template <typename T> inline bool umax (T &a, const T &b) { return (a < b ? a = b, 1 : 0); }
template <typename T> inline bool umin (T &a, const T &b) { return (a > b ? a = b, 1 : 0); }

template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 5e4 + 100;
const int K = 5;

int block[N], ans[N];
vector <int> rblock[N];
vector <pii> g[N], rg[N];

inline void rec (int l, int r, vector <tuple <int, int, int>> query) {
    if (l >= r) return;
    int mid = (l + r) >> 1;

    vector <vector <int>> dist (K, vector <int> (20, 1e9));
    const int norm = rblock[mid][0];

    for (auto st : rblock[mid]) {
        priority_queue <pii, vector <pii>, greater <pii>> pq;
        pq.push({0, st}); dist[st - norm][st] = 0;

        while (!pq.empty()) {
            auto [d, v] = pq.top(); pq.pop();
            if (d > dist[st - norm][v]) continue;
            for (auto [u, w] : rg[v]) {
                if (dist[st - norm][u] > dist[st - norm][v] + w) {
                    dist[st - norm][u] = dist[st - norm][v] + w;
                    pq.push({dist[st - norm][u], u});
                }
            }
        }

        pq.push({0, st});
        while (!pq.empty()) {
            auto [d, v] = pq.top(); pq.pop();
            if (d > dist[st - norm][v]) continue;
            for (auto [u, w] : g[v]) {
                if (dist[st - norm][u] > dist[st - norm][v] + w) {
                    dist[st - norm][u] = dist[st - norm][v] + w;
                    pq.push({dist[st - norm][u], u});
                }
            }
        }
    }

    vector <tuple <int, int, int>> left, right;
    for (auto [l, r, idx] : query) {
        if (block[r] < mid) left.pb({l, r, idx});
        else if (block[l] > mid) right.pb({l, r, idx});
        else {
            for (auto j : rblock[mid]) {
                umin(ans[idx], dist[j - norm][l] + dist[j - norm][r]);
            }
        }
    }

    rec(l, mid - 1, left);
    rec(mid + 1, r, right);
}

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int k, n, m, q; cin >> k >> n >> m >> q;
    for (int i = 0; i < n; i++) {
        block[i] = i / k;
        rblock[i / k].pb(i);
    }
    for (int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        g[a].pb({b, c});
        rg[b].pb({a, c});
    }
    vector <tuple <int, int, int>> query (q);
    for (int i = 0; i < q; i++) {
        int a, b; cin >> a >> b;
        query[i] = {a, b, i};
    }
    fill(ans, ans + q, 1e9);
    rec(0, block[n - 1], query);
    for (int i = 0; i < q; i++) cout << (ans[i] == 1e9 ? -1 : ans[i]) << endl;
    return 0;
}

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