Submission #1120053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120053		ksujay2	Escape Route 2 (JOI24_escape2)	C++17	100 / 100	890 ms	59464 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int BSZ = 300;
const ll INF = 1e18;
void upd(ll& x, ll y) { x = min(x, y); }
int main() {
    int N, T; cin >> N >> T;
    vector<vector<int>> A(N), B(N);
    vector<int> M(N);
    for(int i = 0; i < N - 1; i++) {
        int Mi;
        cin >> Mi;
        vector<int> imp;
        map<int, vector<int>> mp;
        for(int j = 0; j < Mi; j++) {
            int A, B; cin >> A >> B;
            mp[A].push_back(B);
            imp.push_back(A);
        }
        sort(imp.begin(), imp.end());
        imp.resize(unique(imp.begin(), imp.end())-imp.begin());
        reverse(imp.begin(), imp.end());
        int E = T;
        for(int j : imp) {
            bool nw = false;
            for(int e : mp[j]) {
                if(E > e) E = e, nw = true;
            }
            if(nw) {
                A[i].push_back(j);
                B[i].push_back(E);
                M[i]++;
            }
        }
        reverse(A[i].begin(), A[i].end());
        reverse(B[i].begin(), B[i].end());
        A[i].push_back(A[i][0] + T);
        B[i].push_back(B[i][0] + T);
    }

    int Q; cin >> Q;
    vector<vector<pair<int, int>>> queries(N);
    for(int i = 0; i < Q; i++) {
        int L, R; cin >> L >> R;
        queries[L-1].push_back({R-1, i});
    }
    vector<vector<int>> nxt(N);
    vector<vector<vector<int>>> prv(N);
    for(int i = 0; i < N; i++) {
        nxt[i].resize(M[i]);
        prv[i].resize(M[i]);
    }
    for(int i = 0; i < N - 2; i++) {
        int k = 0;
        for(int j = 0; j < M[i]; j++) {
            while(B[i][j] > A[i+1][k]) k++;
            nxt[i][j] = k;
            prv[i + 1][k % M[i+1]].push_back(j);
        }
    }
    vector<ll> ans(Q, INF);
    vector<vector<ll>> D(N);
    for(int i = 0; i < N; i++) {
        if(M[i] > BSZ) {
            D[i].assign(M[i], INF);
            for(int j = 0; j < M[i]; j++) D[i][j] = 0;
            for(int j = i; j < N - 2; j++) {
                D[j + 1].assign(M[j + 1], INF);
                for(int k = 0; k < M[j]; k++) {
                    upd(D[j + 1][nxt[j][k] % M[j + 1]], D[j][k] + A[j + 1][nxt[j][k]] - A[j][k]);
                }
            }
            vector<ll> rans(N, INF);
            for(int j = i; j < N - 1; j++) {
                for(int k = 0; k < M[j]; k++) {
                    upd(rans[j + 1], D[j][k] + B[j][k] - A[j][k]);
                }
            }
            for(auto [u, v] : queries[i]) {
                ans[v] = rans[u];
            }
        }
    }
    vector<int> h(N);
    vector<ll> d(N);
    function<void(int, int)> dfs = [&] (int i, int j) {
        if(M[i] <= BSZ) {
            for(auto [u, v] : queries[i]) {
                upd(ans[v], B[u-1][h[u-1]] - A[u-1][h[u-1]] + d[i] - d[u-1]);
            }
        }
        for(int u : prv[i][j]) {
            h[i-1] = u;
            d[i-1] = d[i] + A[i][nxt[i-1][u]] - A[i-1][u];
            dfs(i-1, u);
        }
    };
    for(int i = 0; i < M[N-2]; i++) {
        h[N-2] = i;
        dfs(N - 2, i);
    }
    for(ll a : ans) cout << a << endl;
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 17 / 17
• Subtask 4: 23 / 23
• Subtask 5: 36 / 36
• Subtask 6: 10 / 10