제출 #1261147

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1261147		inkvizytor	Passport (JOI23_passport)	C++20	22 / 100	525 ms	118104 KiB

passport

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

using ll = long long;
const ll INF = (1LL<<60);

void add(int v, int L, int R,
         vector<vector<pair<ll,int>>> &g,
         int a, int b, int x) {
    if (a <= L && R <= b) {
        g[v].push_back({1, x});
        return;
    }
    if (b < L || R < a) return;
    int mid = (L + R) >> 1;
    add(v<<1,     L,     mid, g, a, b, x);
    add(v<<1|1, mid+1,     R, g, a, b, x);
}

void dijkstra(int s,
              const vector<vector<pair<ll,int>>> &g,
              vector<ll> &dist) {
    fill(dist.begin(), dist.end(), INF);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [d, v] = pq.top(); pq.pop();
        if (d != dist[v]) continue;
        for (auto [w, u] : g[v]) {
            if (dist[u] > d + w) {
                dist[u] = d + w;
                pq.push({dist[u], u});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<pair<int,int>> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i].first >> p[i].second;
        --p[i].first;
        --p[i].second;
    }

    const int N     = 1 << 18;
    const int AGG   = 2 * N;
    const int SRC_L = 2 * N + 1;
    const int SRC_R = 2 * N + 2;
    const int GSZ   = SRC_R + 1;

    vector<vector<pair<ll,int>>> g(GSZ);
    for (int i = 1; i < N; i++) {
        g[i<<1].push_back({0, i});
        g[i<<1|1].push_back({0, i});
    }
    for (int i = 0; i < n; i++) {
        if (p[i].first == 0)     g[SRC_L].push_back({0, N + i});
        if (p[i].second == n-1)  g[SRC_R].push_back({0, N + i});
        add(1, 0, N-1, g, p[i].first, p[i].second, N + i);
    }
    vector<ll> distL(GSZ), distR(GSZ), dist(GSZ);
    dijkstra(SRC_L, g, distL);
    dijkstra(SRC_R, g, distR);
    for (int i = 0; i < 2 * N; i++) {
        if (distL[i] >= INF/2 || distR[i] >= INF/2) continue;
        g[AGG].push_back({distL[i] + distR[i], i});
    }

    dijkstra(AGG, g, dist);

    int q; cin >> q;
    while (q--) {
        int x; cin >> x; --x;
        ll ans = dist[N + x];
        if (ans >= INF/2) cout << -1 << '\n';
        else              cout << ans + 1 << '\n';
    }
    return 0;
}

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