Submission #1128456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128456		Mikael639	Toll (BOI17_toll)	C++20	100 / 100	220 ms	12380 KiB

toll

#include <bits/stdc++.h>

#define fi first
#define se second

#define For(i, a, b) for (int i = (a); i <= (b); ++i)
#define ForD(i, a, b) for (int i = (a); i >= (b); --i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repD(i, n) for (int i = (n) - 1; i >= 0; --i)
#define coutE(x) {cout << x << '\n'; return;}
#define pb push_back
#define pf push_front

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define bs binary_search
#define ub upper_bound
#define lb lower_bound

#define endl '\n'

#define db long double
#define ll long long
#define ii pair<int, int>
#define vi vector<int>
#define vii vector<ii>

using namespace std;

void file(string s){

    if (s.empty()) return;

    freopen((s + ".inp").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

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

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

const int N = 1e5 + 5;
const ll LINF = 1e18;

int n, k, m, q;
vii g[N][2];
ii quer[N];
ll dist[10][N], ans[N];

bool ok(int u, int L, int R){
    return L <= u/k && u/k <= R;
}

void dijkstra(int s, ll* dist, int L, int R, bool t){

    //0 tang
    //1 giam

    For(i, L * k, (R + 1) * k - 1)
        dist[i] = LINF;

    priority_queue<ii, vii, greater<ii>> q;
    dist[s] = 0;
    q.push({0, s});

    while (!q.empty()){
        auto [d, u] = q.top(); q.pop();
        if (dist[u] < d) continue;

        for (auto [v, w]: g[u][t]) if (ok(v, L, R)){
            if (minimize(dist[v], dist[u] + w)){
                q.push({dist[v], v});
            }
        }
    }
}

void dnc(int L, int R, vi& idx){
    if (L >= R) return;

    int mid = (L + R) >> 1;
    rep(i, k){
        dijkstra(mid * k + i, dist[i], mid, R, 0);
        dijkstra(mid * k + i, dist[i], L, mid, 1);
    }

    vi left, right;
    for (int i: idx){
        auto [u, v] = quer[i];
        if (u/k <= mid && mid <= v/k){
            rep(x, k){
                minimize(ans[i], dist[x][u] + dist[x][v]);
            }
        }

        if (v/k < mid) left.pb(i);
        if (u/k > mid) right.pb(i);
    }

    if (!left.empty()) dnc(L, mid - 1, left);
    if (!right.empty()) dnc(mid + 1, R, right);
}

signed main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    file("");

    cin >> k >> n >> m >> q;
    rep(i, m){
        int u, v, w; cin >> u >> v >> w;
        g[u][0].pb({v, w}); g[v][1].pb({u, w});
    }

    vi idx;
    rep(i, q){
        int u, v; cin >> u >> v;
        ans[i] = LINF;
        if (u/k <= v/k){
            idx.pb(i);
            quer[i] = {u, v};
        }
    }

    dnc(0, (n - 1)/k, idx);

    rep(i, q) cout << (ans[i] == LINF ? -1 : ans[i]) << '\n';

    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'void file(std::string)':
toll.cpp:34:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     freopen((s + ".inp").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:35:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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