Submission #1308134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308134		duongquanghai08	Passport (JOI23_passport)	C++20	100 / 100	482 ms	84128 KiB

passport

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

const int N = 200005;
const int INF = 1e9 + 7;

int n, q;
int L[N], R[N];
vector<pair<int, int>> adj[6 * N];
int distL[6 * N], distR[6 * N], distAns[6 * N];
int node_cnt;

void build(int id, int l, int r) {
    node_cnt = max(node_cnt, id + n);
    if (l == r) {
        adj[l].push_back({id + n, 0});
        return;
    }
    int mid = (l + r) >> 1;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    adj[id * 2 + n].push_back({id + n, 0});
    adj[id * 2 + 1 + n].push_back({id + n, 0});
}

void add(int id, int l, int r, int u, int v, int city) {
    if (l > v || r < u) return;
    if (l >= u && r <= v) {
        adj[id + n].push_back({city, 1});
        return;
    }
    int mid = (l + r) >> 1;
    add(id * 2, l, mid, u, v, city);
    add(id * 2 + 1, mid + 1, r, u, v, city);
}

void bfs(int* d, vector<int>& src, int val) {
    fill(d, d + node_cnt + 1, INF);
    deque<int> dq;
    for (int u : src) {
        d[u] = val;
        dq.push_back(u);
    }
    while (!dq.empty()) {
        int u = dq.front();
        dq.pop_front();
        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                if (w == 0) dq.push_front(v);
                else dq.push_back(v);
            }
        }
    }
}

void solve_ans() {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (int i = 1; i <= node_cnt; i++) {
        if (distAns[i] < INF) pq.push({distAns[i], i});
    }
    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if (d > distAns[u]) continue;
        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (distAns[v] > d + w) {
                distAns[v] = d + w;
                pq.push({distAns[v], v});
            }
        }
    }
}

void Solve() {
    cin >> n;
    node_cnt = n;
    build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        cin >> L[i] >> R[i];
        add(1, 1, n, L[i], R[i], i);
    }

    vector<int> srcL, srcR;
    for (int i = 1; i <= n; i++) {
        if (L[i] == 1) srcL.push_back(i);
        if (R[i] == n) srcR.push_back(i);
    }

    bfs(distL, srcL, 1);
    bfs(distR, srcR, 1);

    for (int i = 1; i <= node_cnt; i++) distAns[i] = INF;
    for (int i = 1; i <= n; i++) {
        if (distL[i] < INF && distR[i] < INF) {
            distAns[i] = distL[i] + distR[i] - 1;
        }
    }

    solve_ans();

    cin >> q;
    while (q--) {
        int x; cin >> x;
        if (distAns[x] >= INF) cout << -1 << "\n";
        else cout << distAns[x] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    // freopen("Passport.inp", "r", stdin);
    // freopen("Passport.out", "w", stdout);
    Solve();
    return 0;
}

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