Submission #927015

#	Time	Username	Problem	Language	Result	Execution time	Memory
927015		caterpillow	Passport (JOI23_passport)	C++17	100 / 100	1470 ms	205796 KiB

passport

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll,ll>;
#define vt vector
#define f first
#define s second
#define all(x) x.begin(), x.end() 
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define F0R(i, b) FOR(i, 0, b)
#define endl '\n'
#define debug(x) do{auto _x = x; cerr << #x << " = " << _x << endl;} while(0)
const ll INF = 1e18;

/*

connect cities to their ranges via segtree trick

we solve backwards, so instead of going from country -> all countries in its range
we go from country -> all the ranges that contain this country

we build edges going up the segtree, and connect down from ranges to their source

bfs from left and right endpoints by starting the bfs from the leftmost and rightmost point
then combine values for both ranges
then use those values to do a final dijkstra to get min cost for each node

*/

const ll sz = 1 << 18;

void get_nodes(int l, int r, vt<int>& res) {
    for (l += sz, r += sz + 1; l < r; l /= 2, r /= 2) {
        if (l & 1) res.pb(l++);
        if (r & 1) res.pb(--r);
    }
}

ll n;
vt<pl> ranges;
vt<pl> adj[2 * sz]; // make outgoing edges weight 1
pl dist[2 * sz];

main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    ranges.resize(n);
    fill(dist, dist + 2 * sz, make_pair(INF, INF));
    F0R (i, n) {
        int l, r; cin >> l >> r;
        ranges[i] = {l - 1, r - 1};
    }
    FOR (i, 2, 2 * sz) adj[i].pb({i / 2, 0}); // build segtree

    vt<int> lefts, rights;

    F0R (i, n) {
        auto [l, r] = ranges[i];
        if (l == 0) lefts.pb(i);
        if (r == n - 1) rights.pb(i);
        vt<int> res;
        get_nodes(l, r, res);
        for (int v : res) {
            // cerr << "connected " << v << " to " << i + sz << endl;
            adj[v].pb({i + sz, 1});
        }
    }

    auto bfs = [&](int isf) {
        deque<pl> q;

        if (isf) {
            for (int u : lefts) q.pb({u + sz, 0});
        } else {
            for (int u : rights) q.pb({u + sz, 0});
        }


        while (q.size()) {
            auto [u, d] = q.front();
            q.pop_front();
            if (isf) {
                if (dist[u].f <= d) continue;
                dist[u].f = d;
            } else {
                if (dist[u].s <= d) continue;
                dist[u].s = d;
            }
            for (auto [v, w] : adj[u]) {
                if (w) q.pb({v, d + w});
                else q.push_front({v, d});
            }
        }
    };

    bfs(true);
    bfs(false);

    priority_queue<pl, vt<pl>, greater<pl>> pq;
    FOR (i, sz, n + sz) {
        pq.push({dist[i].f + dist[i].s, i});
    }

    vt<ll> fdist(2 * sz, INF);
    
    while (pq.size()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (fdist[u] <= d) continue;
        fdist[u] = d;
        for (auto [v, w] : adj[u]) {
            pq.push({d + w, v});
        }
    }

    int q; cin >> q;
    F0R (i, q) {
        int u; cin >> u;
        u += sz - 1;
        ll cost = fdist[u];
        if (cost > 696969) cout << "-1\n";
        else cout << cost + 1 << endl; // i dont know why i need to add 1
    }
}

Compilation message (stderr)

passport.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main() {
      | ^~~~

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