Submission #889896

#	Time	Username	Problem	Language	Result	Execution time	Memory
889896		shivensinha4	Passport (JOI23_passport)	C++17	100 / 100	738 ms	91488 KiB

passport

#pragma GCC optimize("unroll-loops")
#include "bits/stdc++.h"
#ifdef mlocal
#include "./Competitive-Code-Library/snippets/prettyprint.h"
#endif
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
#define endl '\n'

class SegmentTree {
private:
    vector<vi> tree; vector<ll> raw; int n;

    void update(int i, int j, int v, int l, int r, int p) {
        if (l > j or r < i) return;
        if (l >= i and r <= j) {
            tree[p].push_back(v);
            return;
        }

        int mid = (l + r) / 2;
        int c1 = 2*p+1, c2 = 2*p+2;
        update(i, j, v, l, mid, c1); update(i, j, v, mid+1, r, c2);
    }

    vi get(int i, int l, int r, int p) {
        if (l > i or r < i) return {};

        vi ans = tree[p];
        tree[p].clear();

        if (l != r) {
            int mid = (l + r) / 2;
            int c1 = 2*p+1, c2 = 2*p+2;
            auto al = get(i, l, mid, c1), ar = get(i, mid+1, r, c2);
            ans.insert(ans.end(), al.begin(), al.end());
            ans.insert(ans.end(), ar.begin(), ar.end());
        }

        return ans;
    }

public:
    SegmentTree(int n): n(n) {
        tree.resize(4*n);
    }

    void update(int i, int j, int v) {
        update(i, j, v, 0, n-1, 0);
    }

    vi get(int i) {
        return get(i, 0, n-1, 0);
    }
};


const int INF = 1e9;

int main() {
#ifdef mlocal
    freopen("test.in", "r", stdin);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n; cin >> n;
    vector<ii> seg(n);
    SegmentTree tree(n);
    for_(i, 0, n){
        cin >> seg[i][0] >> seg[i][1], seg[i][0]--, seg[i][1]--;
        tree.update(seg[i][0], seg[i][1], i);
    }

    function<vi(int)> bfs = [&] (int s) {
        vi dist(n, INF);
        dist[s] = 0;

        queue<int> q;
        q.push(s);

        auto curr_tree = tree;

        while (q.size()) {
            auto p = q.front(); q.pop();
            auto adj = curr_tree.get(p);
            for (auto i: adj) if (dist[i] == INF) {
                dist[i] = dist[p] + 1;
                q.push(i);
            }
        }
        return dist;
    };

    vi ans = bfs(0);
    {
        vi ans2 = bfs(n - 1);
        for_(i, 0, n) ans[i] += ans2[i];
    }
    for_(i, 1, n - 1) if (ans[i] < INF) ans[i]--;

    const int pq_size = 2 * n + 10;
    vector<vi> pq(pq_size);
    int dist = 0;

    for_(i, 0, n) if (ans[i] < INF) pq[ans[i]].push_back(i);

    while (true) {
        while (dist < pq_size and pq[dist].empty()) dist++;
        if (dist == pq_size) break;

        int p = pq[dist].back(); pq[dist].pop_back();
        if (dist != ans[p]) continue;

        auto adj = tree.get(p);

        for (auto i: adj) {
            if (ans[i] > ans[p] + 1) {
                ans[i] = ans[p] + 1;
                pq[ans[i]].push_back(i);
            }
        }
    }

    int q; cin >> q;
    while (q--) {
        int p; cin >> p;
        p--;

        cout << (ans[p] >= INF ? -1 : ans[p]) << endl;
    }
}

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