Submission #1086560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086560		adaawf	Passport (JOI23_passport)	C++17	100 / 100	616 ms	96536 KiB

passport

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
vector<pair<int, int>> t[1000005];
int f[1000005], g[1000005], d[1000005], n;
void build(int v, int tl, int tr) {
    if (tl == tr) {
        t[tl].push_back({v + n, 0});
        return;
    }
    int mid = (tl + tr) / 2;
    build(v * 2, tl, mid);
    build(v * 2 + 1, mid + 1, tr);
    t[v * 2 + n].push_back({v + n, 0});
    t[v * 2 + 1 + n].push_back({v + n, 0});
}
void update(int v, int tl, int tr, int l, int r, int x) {
    if (l > r) return;
    if (tl == l && tr == r) {
        t[v + n].push_back({x, 1});
        return;
    }
    int mid = (tl + tr) / 2;
    update(v * 2, tl, mid, l, min(r, mid), x);
    update(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r, x);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        update(1, 1, n, l, r, i);
    }
    priority_queue<pair<int, int>> q;
    memset(f, 0x3f, sizeof f);
    memset(g, 0x3f, sizeof g);
    memset(d, 0x3f, sizeof d);
    f[1] = 0; g[n] = 0;
    q.push({0, 1});
    while (!q.empty()) {
        pair<int, int> p = q.top();
        q.pop();
        int x = -p.first, u = p.second;
        if (f[u] != x) continue;
        for (auto w : t[u]) {
            if (f[w.first] > f[u] + w.second) {
                f[w.first] = f[u] + w.second;
                q.push({-f[w.first], w.first});
            }
        }
    }
    q.push({0, n});
    while (!q.empty()) {
        pair<int, int> p = q.top();
        q.pop();
        int x = -p.first, u = p.second;
        if (g[u] != x) continue;
        for (auto w : t[u]) {
            if (g[w.first] > g[u] + w.second) {
                g[w.first] = g[u] + w.second;
                q.push({-g[w.first], w.first});
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (i == 1 || i == n) {
            d[i] = f[i] + g[i];
        }
        else d[i] = f[i] + g[i] - 1;
        q.push({-d[i], i});
    }
    while (!q.empty()) {
        pair<int, int> p = q.top();
        q.pop();
        int x = -p.first, u = p.second;
        if (d[u] != x) continue;
        for (auto w : t[u]) {
            if (d[w.first] > d[u] + w.second) {
                d[w.first] = d[u] + w.second;
                q.push({-d[w.first], w.first});
            }
        }
    }
    int qq;
    cin >> qq;
    for (int jj = 0; jj < qq; jj++) {
        int x;
        cin >> x;
        if (d[x] > 1e9) cout << -1;
        else cout << d[x];
        cout << '\n';
    }
}

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