Submission #1305733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305733		SkillIssueWAGuy	Escape Route 2 (JOI24_escape2)	C++20	0 / 100	1 ms	560 KiB

Main

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

int sqrtN = 345;
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, 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}
    int d1 = d%sqrtN, d2 = d/sqrtN;
    if (d1 == 0) return Pb[x][y][d2-1];
    else if (d2 == 0) return Ps[x][y][d1-1];
    return {Pb[x+d1][Ps[x][y][d1-1].first][d2-1].first, Ps[x][y][d1-1].second + Pb[x+d1][Ps[x][y][d1-1].first][d2-1].second};
}
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 = 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] = 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 + G[i+1][0].first};
            }
            else {
                G[i][j] = {p, G[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[i].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++) {
            Pb[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 < Pb[i].size(); k++){
                Pb[j][k].push_back({Pb[j+i*sqrtN][Pb[j][k][i-1].first][0].first, Pb[j][k][i-1].second + Pb[j+i*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++) {}
    return 0;
}

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