Submission #991994

#	Time	Username	Problem	Language	Result	Execution time	Memory
991994		onbert	Passport (JOI23_passport)	C++17	100 / 100	587 ms	46928 KiB

passport

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 20, m = 450, INF = 1e9;
pair<int,int> Lcost[maxn];
bool cmpl(int a, int b) {
    return Lcost[a].second < Lcost[b].second;
}
pair<int,int> Rcost[maxn];
bool cmpr(int a, int b) {
    return Rcost[a].second < Rcost[b].second;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    pair<int,int> a[n+1];
    vector<pair<int,int>> Lpos[m], Lpos1[m];
    vector<pair<int,int>> lpos[n+1], lpos1[n+1];
    for (int i=1;i<=n;i++) {
        cin >> a[i].first >> a[i].second;
        Lpos1[a[i].first/m].push_back({a[i].second, i});
        lpos1[a[i].first].push_back({a[i].second, i});
    }
    for (int i=0;i<m;i++) sort(Lpos1[i].begin(), Lpos1[i].end());
    for (int i=0;i<=n;i++) sort(lpos1[i].begin(), lpos1[i].end());

    for (int i=0;i<m;i++) Lpos[i] = Lpos1[i];
    for (int i=1;i<=n;i++) lpos[i] = lpos1[i];
    bool vis[n+1];
    for (int i=1;i<=n;i++) vis[i] = false;
    vis[n] = true;
    vector<int> from = {n}, to;
    int rcost[n+1];
    for (int i=1;i<=n;i++) rcost[i] = INF;
    for (int cost=-1; from.size()>0; cost++) {
        for (int u:from) rcost[u] = max(cost, (int)0);
        for (int u:from) {
            for (int L=0;(L+1)*m-1<=u;L++) {
                while (Lpos[L].size()>0 && Lpos[L].back().first>=u) {
                    int v = Lpos[L].back().second;
                    if (!vis[v]) to.push_back(v);
                    vis[v] = true;
                    Lpos[L].pop_back();
                }
            }
            int l = u/m*m;
            for (;l<=u;l++) {
                // if (lpos[l].size()>0) cout << "test " << lpos[l].back().first << endl;
                while (lpos[l].size()>0 && lpos[l].back().first>=u) {
                    int v = lpos[l].back().second;
                    // if (!vis[v]) cout << cost << " " << u << " " << v << endl;
                    if (!vis[v]) to.push_back(v);
                    vis[v] = true;
                    lpos[l].pop_back();
                }
            }
        }
        from.clear();
        swap(to, from);
    }

    for (int i=0;i<m;i++) Lpos[i] = Lpos1[i];
    for (int i=1;i<=n;i++) lpos[i] = lpos1[i];
    for (int i=1;i<=n;i++) vis[i] = false;
    vis[1] = true;
    from = {1};
    for (int i=1;i<=n;i++) Lcost[i] = {INF, INF};
    Lcost[1].second = rcost[1] + 1;
    for (int cost=0; from.size()>0; cost++) {
        sort(from.begin(), from.end(), cmpl);
        for (int u:from) Lcost[u].first = cost;
        for (int u:from) {
            for (int L=0;(L+1)*m-1<=u;L++) {
                while (Lpos[L].size()>0 && Lpos[L].back().first>=u) {
                    int v = Lpos[L].back().second;
                    if (!vis[v]) {
                        to.push_back(v);
                        Lcost[v].second = min(rcost[v], Lcost[u].second);
                    }
                    vis[v] = true;
                    Lpos[L].pop_back();
                }
            }
            int l = u/m*m;
            for (;l<=u;l++) {
                while (lpos[l].size()>0 && lpos[l].back().first>=u) {
                    int v = lpos[l].back().second;
                    if (!vis[v]) {
                        to.push_back(v);
                        Lcost[v].second = min(rcost[v], Lcost[u].second);
                    }
                    vis[v] = true;
                    lpos[l].pop_back();
                }
            }
        }
        from.clear();
        swap(to, from);
    }


    //2nd set of ans
    for (int i=0;i<m;i++) Lpos[i] = Lpos1[i];
    for (int i=1;i<=n;i++) lpos[i] = lpos1[i];
    for (int i=1;i<=n;i++) vis[i] = false;
    vis[1] = true;
    from = {1};
    to.clear();
    int lcost[n+1];
    for (int i=1;i<=n;i++) lcost[i] = INF;
    for (int cost=-1; from.size()>0; cost++) {
        for (int u:from) lcost[u] = max(cost, (int)0);
        for (int u:from) {
            for (int L=0;(L+1)*m-1<=u;L++) {
                while (Lpos[L].size()>0 && Lpos[L].back().first>=u) {
                    int v = Lpos[L].back().second;
                    if (!vis[v]) to.push_back(v);
                    vis[v] = true;
                    Lpos[L].pop_back();
                }
            }
            int l = u/m*m;
            for (;l<=u;l++) {
                while (lpos[l].size()>0 && lpos[l].back().first>=u) {
                    int v = lpos[l].back().second;
                    if (!vis[v]) to.push_back(v);
                    vis[v] = true;
                    lpos[l].pop_back();
                }
            }
        }
        from.clear();
        swap(to, from);
    }

    for (int i=0;i<m;i++) Lpos[i] = Lpos1[i];
    for (int i=1;i<=n;i++) lpos[i] = lpos1[i];
    for (int i=1;i<=n;i++) vis[i] = false;
    vis[n] = true;
    from = {n};
    for (int i=1;i<=n;i++) Rcost[i] = {INF, INF};
    Rcost[1].second = lcost[1] + 1;
    for (int cost=0; from.size()>0; cost++) {
        sort(from.begin(), from.end(), cmpr);
        for (int u:from) Rcost[u].first = cost;
        for (int u:from) {
            for (int L=0;(L+1)*m-1<=u;L++) {
                while (Lpos[L].size()>0 && Lpos[L].back().first>=u) {
                    int v = Lpos[L].back().second;
                    if (!vis[v]) {
                        to.push_back(v);
                        Rcost[v].second = min(lcost[v], Rcost[u].second);
                    }
                    vis[v] = true;
                    Lpos[L].pop_back();
                }
            }
            int l = u/m*m;
            for (;l<=u;l++) {
                while (lpos[l].size()>0 && lpos[l].back().first>=u) {
                    int v = lpos[l].back().second;
                    if (!vis[v]) {
                        to.push_back(v);
                        Rcost[v].second = min(lcost[v], Rcost[u].second);
                    }
                    vis[v] = true;
                    lpos[l].pop_back();
                }
            }
        }
        from.clear();
        swap(to, from);
    }
    
    int q;
    cin >> q;
    for (int i=0;i<q;i++) {
        int pos;
        cin >> pos;
        int ans = min(Lcost[pos].first + Lcost[pos].second, Rcost[pos].first + Rcost[pos].second);
        if (ans >= INF) cout << "-1\n";
        else cout << ans << "\n";
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 46 / 46