Submission #951092

#	Time	Username	Problem	Language	Result	Execution time	Memory
951092		blackslex	Passport (JOI23_passport)	C++17	48 / 100	2133 ms	1048576 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, vector<pii>());
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &L[i], &R[i]);
        for (int j = L[i]; j <= R[i]; j++) v[j].emplace_back(i, 1);
    }
    scanf("%d", &q);
    vector<int> d(n + 5, 1e9), d2(n + 5, 1e9), ans(n + 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:14:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         scanf("%d %d", &L[i], &R[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
passport.cpp:40:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     while (q--) scanf("%d", &x), printf("%d\n", ans[x] == 1e9 ? -1 : ans[x]);
      |                 ~~~~~^~~~~~~~~~

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