Submission #951097

#	Time	Username	Problem	Language	Result	Execution time	Memory
951097		blackslex	Passport (JOI23_passport)	C++17	100 / 100	817 ms	99764 KiB

passport

#include<bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

int n, q, x;
vector<vector<pii>> v;

int main() {
    scanf("%d", &n);
    vector<int> L(n + 5), R(n + 5);
    v.resize(n * 5 + 5, vector<pii>());
    auto build = [&] (auto &&build, int l, int r, int idx) {
        if (l == r) return void(v[l].emplace_back(idx + n, 0));
        int mid = (l + r) >> 1;
        build(build, l, mid, idx * 2);
        build(build, mid + 1, r, idx * 2 + 1);
        v[idx * 2 + n].emplace_back(idx + n, 0);
        v[idx * 2 + 1 + n].emplace_back(idx + n, 0);
    };
    auto upd = [&] (auto &&upd, int l, int r, int idx, int tl, int tr, int curidx) {
        if (l > tr || r < tl) return;
        if (l >= tl && r <= tr) return void(v[idx + n].emplace_back(curidx, 1));
        int mid = (l + r) >> 1;
        upd(upd, l, mid, idx * 2, tl, tr, curidx);
        upd(upd, mid + 1, r, idx * 2 + 1, tl, tr, curidx);
    };
    build(build, 1, n, 1);
    for (int i = 1; i <= n; i++) scanf("%d %d", &L[i], &R[i]), upd(upd, 1, n, 1, L[i], R[i], i);
    scanf("%d", &q);
    vector<int> d(n * 5 + 5, 1e9), d2(n * 5 + 5, 1e9), ans(n * 5 + 5, 1e9);
    auto dijk = [&] (int s, vector<int> &curd) {
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        pq.emplace(curd[s] = 0, s);
        while (!pq.empty()) {
            auto [nd, nn] = pq.top(); pq.pop();
            for (auto &[tn, td]: v[nn]) if (curd[tn] > curd[nn] + td) pq.emplace(curd[tn] = curd[nn] + td, tn);
        }
    };
    dijk(1, d); dijk(n, d2);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    for (int i = 1; i <= n; i++) pq.emplace(ans[i] = min(ans[i], d[i] + d2[i] - (i > 1 && i < n)), i);
    priority_queue<pii, vector<pii>, greater<pii>> pq2;
    while (!pq.empty()) {
        auto [nd, nn] = pq.top(); pq.pop();
        pq2.emplace(nd, nn);
    }
    while (!pq2.empty()) pq.emplace(pq2.top()), pq2.pop();
    while (!pq.empty()) {
        auto [nd, nn] = pq.top(); pq.pop();
        for (auto &[tn, td]: v[nn]) if (ans[tn] > ans[nn] + td) pq.emplace(ans[tn] = ans[nn] + td, tn);
    }
    while (q--) scanf("%d", &x), printf("%d\n", ans[x] == 1e9 ? -1 : ans[x]);
}

Compilation message (stderr)

passport.cpp: In function 'int main()':
passport.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
passport.cpp:29:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     for (int i = 1; i <= n; i++) scanf("%d %d", &L[i], &R[i]), upd(upd, 1, n, 1, L[i], R[i], i);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
passport.cpp:53:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     while (q--) scanf("%d", &x), printf("%d\n", ans[x] == 1e9 ? -1 : ans[x]);
      |                 ~~~~~^~~~~~~~~~

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