Submission #1261136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261136		inkvizytor	Tourism (JOI23_tourism)	C++20	0 / 100	43 ms	49836 KiB

tourism

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

#define int long long

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

void dij(int s, vector<vector<pair<int, int>>> &g, vector<int> &w) {
    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();
        if (w[v.second] < 1e9) {
            continue;
        }
        w[v.second] = v.first;
        for (auto u : g[v.second]) {
            if (w[u.second] > v.first+u.first) {
                pq.push({v.first+u.first, u.second});
            }
        }
    }
}

int32_t 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)+10);
    vector<int> s ((1<<19)+10, 1e18), k ((1<<19)+10, 1e18), w ((1<<19)+10, 1e18);
    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++) {
        if (p[i].first == 0) {
            g[(1<<19)+1].push_back({0, (1<<18)+i});
        }
        if (p[i].second == n-1) {
            g[(1<<19)+2].push_back({0, (1<<18)+i});
        }
        add(1, 0, (1<<18)-1, g, p[i].first, p[i].second, (1<<18)+i);
    }
    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: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41