Submission #952651

#	Time	Username	Problem	Language	Result	Execution time	Memory
952651		LOLOLO	Passport (JOI23_passport)	C++17	48 / 100	2109 ms	741828 KiB

passport

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 2e5 + 10;
int lst, ss[N], n;
vector <pair <int, int>> ed[N * 6];

void build(int id, int l, int r) {
    if (l == r) {
        ss[l] = id;
        return;
    }

    int m = (l + r) / 2;
    ed[id * 2].pb({id, 0});
    ed[id * 2 + 1].pb({id, 0});
    build(id * 2, l, m);
    build(id * 2 + 1, m + 1, r);
}

void dfs(int id, int l, int r, int u, int v, int cur) {
    if (l > v || r < u)
        return;

    if (l >= r && u <= v) {
        ed[id].pb({cur, 0});
        return;
    }

    int m = (l + r) / 2;
    dfs(id * 2, l, m, u, v, cur);
    dfs(id * 2 + 1, m + 1, r, u, v, cur);
}

deque <int> dq[N];

void dijkstra(vector <int> &dis, vector <int> save, vector <int> cc) {
    vector <bool> used(lst + 1, 0);
    dis.assign(lst + 1, 2e8);
    priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> pq;

    for (auto x : save) {
        if (cc[x] <= n) {
            dis[x] = cc[x];
            dq[cc[x]].pb(x);
        } 
    }

    for (int i = 0; i <= n; i++) {
        while (sz(dq[i])) {
            int t = dq[i].front();
            dq[i].pop_front();

            if (used[t])
                continue;

            used[t] = 1;
            for (auto x : ed[t]) {
                if (used[x.f])
                    continue;

                if (x.s == 0) {
                    if (dis[x.f] > dis[t]) {
                        dis[x.f] = dis[t];
                        dq[dis[t]].push_back(x.f);
                    }
                } else {
                    if (dis[x.f] > dis[t] + 1) {
                        dis[x.f] = dis[t] + 1;
                        dq[dis[t] + 1].push_back(x.f);
                    }
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    lst = n * 4;
    build(1, 1, n);

    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        lst++;
        ed[lst].pb({ss[i], 1});
        dfs(1, 1, n, l, r, lst);
    }

    vector <int> d1, d2, d3, cst(lst + 1, 0), id;
    dijkstra(d1, {ss[1]}, cst);
    dijkstra(d2, {ss[n]}, cst);

    for (int i = 1; i <= lst; i++) {
        id.pb(i);
        cst[i] = d1[i] + d2[i];
    }

    dijkstra(d3, id, cst);

    int q;
    cin >> q;

    while (q--) {
        int x;
        cin >> x;
        if (d3[ss[x]] >= 1e8) {
            cout << -1 << '\n';
        } else {
            cout << d3[ss[x]] << '\n';
        }
    }


    return 0;
}

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