Submission #952640

#	Time	Username	Problem	Language	Result	Execution time	Memory
952640		LOLOLO	Passport (JOI23_passport)	C++17	48 / 100	983 ms	1048576 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 a[N], b[N], c[N], p[N], lst, ss[N];
vector < vector <int>> save;
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;
    save.pb({id, id * 2, 0});
    save.pb({id, id * 2 + 1, 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) {
        save.pb({cur, id, 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);
}

void dijkstra(vector <ll> &dis, vector <ll> save, vector <ll> cc) {
    dis.assign(lst + 1, 1e17);
    priority_queue <pair <ll, ll>, vector <pair <ll, ll>>, greater <pair <ll, ll>>> pq;

    for (auto x : save) {
        pq.push({cc[x], x});
        dis[x] = cc[x];
    }

    while (sz(pq)) {
        auto t = pq.top();
        pq.pop();
        if (dis[t.s] < t.f) 
            continue;

        for (auto x : ed[t.s]) {
            if (dis[x.f] > t.f + x.s) {
                dis[x.f] = t.f + x.s;
                pq.push({dis[x.f], x.f});
            }
        }
    }
}

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

    int n;
    cin >> n;

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

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

    for (auto x : save) {
        ed[x[1]].pb({x[0], x[2]});
    }

    vector <ll> 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]] > 1e16) {
            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