Submission #1261069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261069		inkvizytor	Passport (JOI23_passport)	C++20	22 / 100	601 ms	108600 KiB

passport

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

#define ll long long

void add(int v, int p, int k, vector<vector<pair<int, int>>> &g, int a, int b, int x, bool q1, bool q2) {
    if (a <= p && k <= b) {
        g[v].push_back({1, x});
        if (q1) {
            g[(1<<19)+1].push_back({0, x});
        }
        if (q2) {
            g[(1<<19)+2].push_back({0, x});
        }
        return;
    }
    if (a > k || b < p) {
        return;
    }
    add(v*2, p, (p+k)/2, g, a, b, x, q1, q2);
    add(v*2+1, (p+k)/2+1, k, g, a, b, x, q1, q2);
}

void dij(int s, vector<vector<pair<int, int>>> &g, vector<int> &w) {
    w[s] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        auto v = pq.top();
        pq.pop();
        for (auto u : g[v.second]) {
            if (w[u.second] > v.first+u.first) {
                pq.push({v.first+u.first, u.second});
                w[u.second] = v.first+u.first;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    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--;
    }
    vector<vector<pair<int, int>>> g ((1<<19)+3);
    vector<int> s ((1<<19)+3, 1e9), k ((1<<19)+3, 1e9), w ((1<<19)+3, 1e9);
    for (int i = 1; i < (1<<18); i++) {
        g[i*2].push_back({0, i});
        g[i*2+1].push_back({0, i});
    }
    for (int i = 0; i < n; i++) {
        int q1 = p[i].first==0, q2 = p[i].second == n-1;
        add(1, 0, (1<<18)-1, g, p[i].first, p[i].second, (1<<18)+i, q1, q2);
    }
    dij((1<<19)+1, g, s);
    dij((1<<19)+2, g, k);
    for (int i = 0; i < (1<<19); i++) {
        g[(1<<19)].push_back({s[i]+k[i], i});
    }
    dij((1<<19), g, w);
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;
        x--;
        if (w[(1<<18)+x] >= 1e9) {
            cout << -1 << '\n';
            continue;
        } 
        cout << w[(1<<18)+x]+1 << '\n';
    }
}

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