Submission #1308164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308164		thuhienne	Passport (JOI23_passport)	C++20	0 / 100	5 ms	568 KiB

passport

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

using ll = long long;
const int inf = 1e9;
const int maxn = 200005;

int n, q_cnt;
pair<int, int> seg[maxn];
int d1[5 * maxn], d2[5 * maxn], d3[5 * maxn];
vector<pair<int, int>> adj[5 * maxn];

// Node 1..n: Các quốc gia
// Node n+1..5n: Các nút trên Segment Tree

void build(int id, int l, int r) {
    if (l == r) {
        // Nối từ nút lá của cây phân đoạn về đỉnh quốc gia tương ứng (trọng số 0)
        adj[id + n].push_back({l, 0});
        return;
    }
    int mid = (l + r) >> 1;
    // Nối từ nút cha xuống nút con (trọng số 0)
    adj[id + n].push_back({id * 2 + n, 0});
    adj[id + n].push_back({id * 2 + 1 + n, 0});
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
}

void add_edge(int id, int l, int r, int u, int v, int from_node) {
    if (l > v || r < u) return;
    if (l >= u && r <= v) {
        // Nối từ quốc gia i đến nút trên cây phân đoạn (trọng số 1)
        adj[from_node].push_back({id + n, 1});
        return;
    }
    int mid = (l + r) >> 1;
    add_edge(id * 2, l, mid, u, v, from_node);
    add_edge(id * 2 + 1, mid + 1, r, u, v, from_node);
}

void dijkstra(int d[]) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (int i = 1; i <= 5 * n; i++) {
        if (d[i] < inf) pq.push({d[i], i});
    }

    while (!pq.empty()) {
        int du = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (du > d[u]) continue;

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int w = edge.second;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> seg[i].first >> seg[i].second;

    build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        add_edge(1, 1, n, seg[i].first, seg[i].second, i);
    }

    fill(d1, d1 + 5 * n + 1, inf);
    fill(d2, d2 + 5 * n + 1, inf);
    fill(d3, d3 + 5 * n + 1, inf);

    // Tìm đường đến 1 và N
    for (int i = 1; i <= n; i++) {
        if (seg[i].first == 1) d1[i] = 1;
        if (seg[i].second == n) d2[i] = 1;
    }

    dijkstra(d1);
    dijkstra(d2);

    // Kết hợp kết quả: d3[i] là chi phí để đi được cả 1 và N
    for (int i = 1; i <= n; i++) {
        if (d1[i] < inf && d2[i] < inf) {
            d3[i] = d1[i] + d2[i] - 1;
        }
    }
    
    // Lan truyền d3 qua các cạnh thuận
    dijkstra(d3);

    cin >> q_cnt;
    while (q_cnt--) {
        int x; cin >> x;
        if (d3[x] >= inf) cout << -1 << "\n";
        else cout << d3[x] << "\n";
    }

    return 0;
}

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