Submission #1264818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264818		Bui_Quoc_Cuong	Toll (BOI17_toll)	C++20	7 / 100	34 ms	10024 KiB

toll

#include <bits/stdc++.h>
template <class A, class B>
    bool maximize (A &a, const B b){
        if (a < b) {
            a = b;
            return true;
        } return false;
    }
template <class A, class B>
    bool minimize (A &a, const B b) {
        if (a > b) {
            a = b;
            return true;
        } return false;
    }
#define FOR(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FORD(i, a, b) for(int i = (a); i >= (int)(b); i--)
#define fi first
#define se second
#define pb push_back
#define ALL(A) A.begin(), A.end()
#define BIT(mask,i) ((mask>>(i))&1)
#define ll long long
using namespace std;

int K, N, M, Q;
vector <pair <int, int>> G[50005], revG[50005];

void init(void) {
    cin >> K >> N >> M >> Q;
    FOR(i, 1, M) {
        int u, v, w; cin >> u >> v >> w;
        G[u].push_back({v, w});
        revG[v].push_back({u, w});
    }
}

namespace sub1 {

    void solve() {
        // Q * M * N * Log
        while (Q--) {
            int sour, fin;
            cin >> sour >> fin;
            vector <long long> dist(N + 2, 1e18);
            priority_queue <array <long long, 2>, vector <array <long long, 2>>, greater <array <long long, 2>>> pq;
            pq.push({dist[sour] = 0, sour});
            while (!pq.empty()) {
                int u = pq.top()[1];
                long long cost = pq.top()[0];
                pq.pop();
                if (cost > dist[u]) continue;
                for (auto it : G[u]) {
                    int v = it.fi, w = it.se;
                    if (minimize(dist[v], cost + w)) {
                        pq.push({dist[v], v});
                    }
                }
            }
            cout << (dist[fin] >= 1e18 ? - 1 : dist[fin]) << "\n";
        }
    }
}

namespace sub2 {
    long long ans[50005];
    vector <array <int, 5>> query;
    vector <int> node[50005];
    long long dist1[50005], dist2[50005];

    #define bg array <long long, 2>
    priority_queue <bg, vector <bg>, greater <bg>> pq;

    void dijk (int id, int L, int R, vector <pair <int, int>> G[], long long dist[]) {
        FOR(i, L, R) for (int &u : node[i]) {
            dist[u] = 1e18;
        }
        for (int &u : node[id]) {
            dist[u] = 0;
            pq.push({0, u});
        }
        while (!pq.empty()) {
            int u = pq.top()[1];
            long long cost = pq.top()[0];
            pq.pop();
            if (cost > dist[u]) continue;
            for (auto it : G[u]) {
                int v = it.fi, w = it.se;
                if ((v / K) < L || (v / K) > R) continue;
                if (minimize(dist[v], cost + w)) {
                    pq.push({dist[v], v});
                }
            }
        }
    }

    void dnc(int L, int R, vector <array <int, 5>> &cur) {
        if (L > R || cur.empty()) return;
        if (L == R) return;
        int mid = (L + R) >> 1;
        vector <array <int, 5>> le, mi, ri;

        for (auto x : cur) {
            if (x[1] <= mid) le.push_back(x);
            else if (x[0] >= mid + 1) ri.push_back(x);
            else mi.push_back(x);
        }   

        dijk(mid, L, R, G, dist1);
        dijk(mid, L, R, revG, dist2);   

        for (auto x : mi) {
            minimize(ans[x[4]], dist2[x[2]] + dist1[x[3]]);
        }

        dnc(L, mid, le);
        dnc(mid + 1, R, ri);
    }   

    void solve() {
        FOR(i, 0, N) dist1[i] = dist2[i] = 1e18;
        FOR(i, 0, N - 1) node[i / K].push_back(i);
        FOR(i, 1, Q) ans[i] = 1e18;
        FOR(i, 1, Q) {
            int u, v; cin >> u >> v;
            if (u == v) {
                ans[i] = 0;
                continue;
            }
            if (v / K <= u / K) continue;
            query.push_back({u / K, v / K, u, v, i});
        }
        dnc(0, N / K, query);
        FOR(i, 1, Q) {
            if (ans[i] >= 1e18) cout << - 1 << "\n";
            else cout << ans[i] << "\n";
        }
    }
}

void process(void) {
    // sub1::solve();
    sub2::solve();
}

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define koa "boi17_toll"
    if (fopen(koa".inp", "r")) {
        freopen(koa".inp", "r", stdin);
        freopen(koa".out", "w", stdout);
    }
    init();
    process();
    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:150:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |         freopen(koa".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:151:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |         freopen(koa".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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