Submission #1305737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305737		SkillIssueWAGuy	Escape Route 2 (JOI24_escape2)	C++20	100 / 100	1840 ms	213092 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e18;

int sqrtN = 19;
int sqrtQ = 183;
int N, T, Q;
vector<vector<pair<int,int>>> F, G; // F is the A[i] B[i] data, G is the pointer to next with cost
vector<vector<vector<pair<int,int>>>> Pb, Pb1, Ps1, Ps; // The large and small sqrt cache, precomputed {pos, cost}
vector<vector<pair<int,int>>> Bs; // first small node encounter, precomputed {pos, cost}
vector<int> Fs; // first small node encounter, index
vector<vector<int>> Cache; // big to big queries, stored in case of repetition
vector<bool> isbig;
pair<int,int> ffind (int x, int y, int d) { // x city y time pair d forward distance return {pos, cost}
    if (d == 0) return {y, 0};
    pair<int,int> cur = {y, 0};
    int d1 = d%sqrtN;
    d /= sqrtN;
    if (d1 != 0) {
        pair<int,int> pp = Ps[x][y][d1-1];
        cur.second += pp.second;
        y = cur.first = pp.first;
        x += d1;
    }
    d1 = d%sqrtN;
    d /= sqrtN;
    if (d1 != 0) {
        pair<int,int> pp = Ps1[x][y][d1-1];
        cur.second += pp.second;
        y = cur.first = pp.first;
        x += d1*sqrtN;
    }
    d1 = d%sqrtN;
    d /= sqrtN;
    if (d1 != 0) {
        pair<int,int> pp = Pb1[x][y][d1-1];
        cur.second += pp.second;
        y = cur.first = pp.first;
        x += d1*sqrtN*sqrtN;
    }
    d1 = d%sqrtN;
    d /= sqrtN;
    if (d1 != 0) {
        pair<int,int> pp = Pb[x][y][d1-1];
        cur.second += pp.second;
        y = cur.first = pp.first;
        x += d1*sqrtN*sqrtN*sqrtN;
    }
    return cur;
}
signed main(){
    cin.sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> T;
    isbig = vector<bool>(N, false);
    Bs = F = G = vector<vector<pair<int,int>>> (N, vector<pair<int,int>>(0));
    Pb = Ps = Ps1 = Pb1 = vector<vector<vector<pair<int,int>>>>(N);
    for (int i = 0; i < N; i++) {
        if (i == N-1) {
            F[i] = G[i] = vector<pair<int,int>>(1, {0,0});
            continue;
        }
        int m;
        cin >> m;
        isbig[i] = (m > sqrtQ);
        F[i] = G[i] = vector<pair<int,int>> (m, {0,0});
        Pb[i] = Ps[i] = Ps1[i] = Pb1[i] = vector<vector<pair<int,int>>> (m);
        // Initialize the rest later
        for (int j = 0; j < m; j++) cin >> F[i][j].first >> F[i][j].second;
        sort(F[i].begin(), F[i].end(), [](pair<int,int> a, pair<int,int> b){
            if (a.first == b.first) return a.second > b.second;
            return a.first < b.first;
        });
        for (int j = m-2; j >= 0; j--) F[i][j].second = min(F[i][j].second, F[i][j+1].second); 
    }
    for (int i = 0; i < G[N-2].size(); i++) {
        G[N-2][i].first = 0;
        G[N-2][i].second = F[N-2][i].second - F[N-2][i].first;
    }
    for (int i = 0; i < N-2; i++) {
        int p = 0;
        for (int j = 0; j < F[i].size(); j++) {
            while (p < F[i+1].size()) {
                if (F[i+1][p].first >= F[i][j].second) break;
                p++;
            }
            if (p == F[i+1].size()) {
                G[i][j] = {0, T - F[i][j].first + F[i+1][0].first};
            }
            else {
                G[i][j] = {p, F[i+1][p].first - F[i][j].first};
            }
            Ps[i][j].push_back(G[i][j]);
        }
    }
    for (int i = 1; i < sqrtN; i++) {
        for (int j = 0; j < N-2; j++) {
            if (j + i + 1 >= N-1) break;
            for (int k = 0; k < Ps[j].size(); k++){
                Ps[j][k].push_back({Ps[j+i][Ps[j][k][i-1].first][0].first, Ps[j][k][i-1].second + Ps[j+i][Ps[j][k][i-1].first][0].second});
            }
        }
    }
    for (int i = 0; i < N-2; i++) {
        if (i + sqrtN >= N-1) break;
        for (int j = 0; j < F[i].size(); j++) {
            Ps1[i][j].push_back(Ps[i][j][sqrtN-1]);
        }
    }
    for (int i = 1; i < sqrtN; i++) {
        for (int j = 0; j < N-2; j++) {
            if (j + (i + 1)*sqrtN >= N-1) break;
            for (int k = 0; k < Ps1[j].size(); k++){
                Ps1[j][k].push_back({Ps1[j+i*sqrtN][Ps1[j][k][i-1].first][0].first, Ps1[j][k][i-1].second + Ps1[j+i*sqrtN][Ps1[j][k][i-1].first][0].second});
            }
        }
    }
    for (int i = 0; i < N-2; i++) {
        if (i + sqrtN*sqrtN >= N-1) break;
        for (int j = 0; j < F[i].size(); j++) {
            Pb1[i][j].push_back(Ps1[i][j][sqrtN-1]);
        }
    }
    for (int i = 1; i < sqrtN; i++) {
        for (int j = 0; j < N-2; j++) {
            if (j + (i + 1)*sqrtN*sqrtN >= N-1) break;
            for (int k = 0; k < Pb1[j].size(); k++){
                Pb1[j][k].push_back({Pb1[j+i*sqrtN*sqrtN][Pb1[j][k][i-1].first][0].first, Pb1[j][k][i-1].second + Pb1[j+i*sqrtN*sqrtN][Pb1[j][k][i-1].first][0].second});
            }
        }
    }
    for (int i = 0; i < N-2; i++) {
        if (i + sqrtN*sqrtN*sqrtN >= N-1) break;
        for (int j = 0; j < F[i].size(); j++) {
            Pb[i][j].push_back(Pb1[i][j][sqrtN-1]);
        }
    }
    for (int i = 1; i < sqrtN; i++) {
        for (int j = 0; j < N-2; j++) {
            if (j + (i + 1)*sqrtN*sqrtN*sqrtN >= N-1) break;
            for (int k = 0; k < Pb[j].size(); k++){
                Pb[j][k].push_back({Pb[j+i*sqrtN*sqrtN*sqrtN][Pb[j][k][i-1].first][0].first, Pb[j][k][i-1].second + Pb[j+i*sqrtN*sqrtN*sqrtN][Pb[j][k][i-1].first][0].second});
            }
        }
    }
    Fs = vector<int> (N, -1);
    Cache = vector<vector<int>> (N);
    for (int i = N-1; i >= 0; i--) {
        if (isbig[i]) {
            Fs[i] = Fs[i+1];
            Cache[i] = vector<int>(Fs[i] - i, -1);
        }
        else Fs[i] = i;
    }
    for (int i = 0; i < N; i++){
        if (!isbig[i]) continue;
        if (Fs[i] == N-1) break;
        Bs[i] = vector<pair<int,int>>(G[Fs[i]].size());
        for (int j = 0; j < Bs[i].size(); j++) Bs[i][j] = {j, MAXN};
        for (int j = 0; j < G[i].size(); j++) {
            auto p = ffind(i, j, Fs[i] - i);
            Bs[i][p.first].second = min(Bs[i][p.first].second, p.second);
        }
        vector<pair<int,int>> pp;
        for (auto j : Bs[i]) if (j.second < MAXN) pp.push_back(j);
        Bs[i] = pp;
    }
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        int d = r - l - 1;
        if (isbig[l]){
            if (r <= Fs[l]) {
                if (Cache[l][d] != -1) {
                    cout << Cache[l][d] << '\n';
                    continue;
                }
                Cache[l][d] = MAXN;
                for (int j = 0; j < F[l].size(); j++){
                    auto p = ffind(l, j, d);
                    Cache[l][d] = min(Cache[l][d], p.second + F[l+d][p.first].second - F[l+d][p.first].first);
                }
                cout << Cache[l][d] << '\n';
                continue;
            }
            int o = MAXN;
            for (int j = 0; j < Bs[l].size(); j++){
                auto p = ffind(Fs[l], Bs[l][j].first, r - Fs[l] - 1);
                p.second += Bs[l][j].second;
                o = min(o, p.second + F[r-1][p.first].second - F[r-1][p.first].first);
            }
            cout << o << '\n';
        }
        else {
            int o = MAXN;
            for (int j = 0; j < F[l].size(); j++){
                auto p = ffind(l, j, d);
                o = min(o, p.second + F[l+d][p.first].second - F[l+d][p.first].first);
            }
            cout << o << '\n';
        }
    }
    return 0;
}

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