Submission #1293611

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293611		altern23	Toll (BOI17_toll)	C++20	100 / 100	146 ms	7700 KiB

toll

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

#define ll int
#define pii pair<ll, ll>
#define fi first
#define sec second

const ll INF = 1e9;
const ll MAXN = 5e4;

ll K, N, M, O, u, v, w, a, b;
pii cur;

vector <ll> kiri, kanan, ans;
vector <vector<pii>> queries, adj;

void dnc(ll l, ll r) {
    if (l >= r) return;

    ll mid = (l + r) / 2;
    
    for (int j = max(0, mid * K); j <= min(N - 1, (mid + 1) * K - 1); j++) {
        kiri[j] = 0;
        for (int k = j - 1; k >= max(0, l * K); --k) {
            kiri[k] = INF;
            for (auto [x, cost] : adj[k]) {
                if (x <= j && x > k) kiri[k] = min(kiri[k], kiri[x] + cost); 
            }
        }

        kanan[j] = 0;
        for (int k = j + 1; k <= min(N - 1, (r + 1) * K - 1); k++) {
            kanan[k] = INF;
            for (auto [x, cost] : adj[k]) {
                if (x >= j && x < k) kanan[k] = min(kanan[k], kanan[x] + cost);
            }
        }
        
        for (int k = j; k >= max(0, l * K); --k) {
            cur = {j, -INF};
            
            // cout << j << "\n";
            // for (auto [x, y] : queries[k]) cout << x << " " << y << " HERE\n";
            
            for (auto it = lower_bound(queries[k].begin(), queries[k].end(), cur); it != queries[k].end() && (*it).fi <= min(N, (r + 1) * K - 1); ++it) {
                // cout << "ya\n";
                // cout << kiri[k] << " " << kanan[(*it).fi] << "\n";
                ans[(*it).sec] = min(ans[(*it).sec], kiri[k] + kanan[(*it).fi]);
            }
        }
    }

    dnc(l, mid - 1);
    dnc(mid + 1, r);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> K >> N >> M >> O;
    
    kiri.resize(N), kanan.resize(N);
    ans.resize(O + 1);

    queries = vector<vector<pii>> (N + 5);
    adj = vector<vector<pii>> (N + 5);

    for (int i = 1; i <= M; i++) {
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    
    for (int i = 1; i <= O; i++) {
        cin >> a >> b;
        queries[a].push_back({b, i});
        ans[i] = INF;
    }

    for (int i = 0; i < N; i++) {
        if (!queries[i].empty()) sort(queries[i].begin(), queries[i].end());
    }

    dnc(0, (N + K) / K - 1);

    for (int i = 1; i <= O; i++) cout << (ans[i] == INF ? -1 : ans[i]) << "\n";
}

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