oj.uz

Submission #927015

# Submission time Handle Problem Language Result Execution time Memory
927015 2024-02-14T06:49:22 Z caterpillow Passport (JOI23_passport) C++17
100 / 100
 1470 ms 205796 KB 
#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

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 41308 KB Output is correct
2 Correct 29 ms 41492 KB Output is correct
3 Correct 27 ms 41292 KB Output is correct
4 Correct 1470 ms 204948 KB Output is correct
5 Correct 406 ms 68112 KB Output is correct
6 Correct 227 ms 63324 KB Output is correct
7 Correct 642 ms 160452 KB Output is correct
8 Correct 173 ms 101392 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 41264 KB Output is correct
2 Correct 28 ms 41252 KB Output is correct
3 Correct 27 ms 41416 KB Output is correct
4 Correct 29 ms 41308 KB Output is correct
5 Correct 27 ms 41300 KB Output is correct
6 Correct 27 ms 41420 KB Output is correct
7 Correct 29 ms 41300 KB Output is correct
8 Correct 34 ms 41440 KB Output is correct
9 Correct 30 ms 41264 KB Output is correct
10 Correct 27 ms 41304 KB Output is correct
11 Correct 29 ms 41468 KB Output is correct
12 Correct 28 ms 41408 KB Output is correct
13 Correct 30 ms 41556 KB Output is correct
14 Correct 28 ms 41576 KB Output is correct
15 Correct 30 ms 41528 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 41264 KB Output is correct
2 Correct 28 ms 41252 KB Output is correct
3 Correct 27 ms 41416 KB Output is correct
4 Correct 29 ms 41308 KB Output is correct
5 Correct 27 ms 41300 KB Output is correct
6 Correct 27 ms 41420 KB Output is correct
7 Correct 29 ms 41300 KB Output is correct
8 Correct 34 ms 41440 KB Output is correct
9 Correct 30 ms 41264 KB Output is correct
10 Correct 27 ms 41304 KB Output is correct
11 Correct 29 ms 41468 KB Output is correct
12 Correct 28 ms 41408 KB Output is correct
13 Correct 30 ms 41556 KB Output is correct
14 Correct 28 ms 41576 KB Output is correct
15 Correct 30 ms 41528 KB Output is correct
16 Correct 32 ms 42404 KB Output is correct
17 Correct 30 ms 41700 KB Output is correct
18 Correct 43 ms 42320 KB Output is correct
19 Correct 33 ms 42292 KB Output is correct
20 Correct 29 ms 41812 KB Output is correct
21 Correct 29 ms 41696 KB Output is correct
22 Correct 43 ms 42116 KB Output is correct
23 Correct 30 ms 42240 KB Output is correct
24 Correct 33 ms 41896 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 41264 KB Output is correct
2 Correct 28 ms 41252 KB Output is correct
3 Correct 27 ms 41416 KB Output is correct
4 Correct 29 ms 41308 KB Output is correct
5 Correct 27 ms 41300 KB Output is correct
6 Correct 27 ms 41420 KB Output is correct
7 Correct 29 ms 41300 KB Output is correct
8 Correct 34 ms 41440 KB Output is correct
9 Correct 30 ms 41264 KB Output is correct
10 Correct 27 ms 41304 KB Output is correct
11 Correct 29 ms 41468 KB Output is correct
12 Correct 28 ms 41408 KB Output is correct
13 Correct 30 ms 41556 KB Output is correct
14 Correct 28 ms 41576 KB Output is correct
15 Correct 30 ms 41528 KB Output is correct
16 Correct 32 ms 42404 KB Output is correct
17 Correct 30 ms 41700 KB Output is correct
18 Correct 43 ms 42320 KB Output is correct
19 Correct 33 ms 42292 KB Output is correct
20 Correct 29 ms 41812 KB Output is correct
21 Correct 29 ms 41696 KB Output is correct
22 Correct 43 ms 42116 KB Output is correct
23 Correct 30 ms 42240 KB Output is correct
24 Correct 33 ms 41896 KB Output is correct
25 Correct 27 ms 41300 KB Output is correct
26 Correct 28 ms 41256 KB Output is correct
27 Correct 33 ms 42392 KB Output is correct
28 Correct 40 ms 41816 KB Output is correct
29 Correct 29 ms 41820 KB Output is correct
30 Correct 30 ms 41820 KB Output is correct
31 Correct 35 ms 42360 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 41308 KB Output is correct
2 Correct 29 ms 41492 KB Output is correct
3 Correct 27 ms 41292 KB Output is correct
4 Correct 1470 ms 204948 KB Output is correct
5 Correct 406 ms 68112 KB Output is correct
6 Correct 227 ms 63324 KB Output is correct
7 Correct 642 ms 160452 KB Output is correct
8 Correct 173 ms 101392 KB Output is correct
9 Correct 30 ms 41264 KB Output is correct
10 Correct 28 ms 41252 KB Output is correct
11 Correct 27 ms 41416 KB Output is correct
12 Correct 29 ms 41308 KB Output is correct
13 Correct 27 ms 41300 KB Output is correct
14 Correct 27 ms 41420 KB Output is correct
15 Correct 29 ms 41300 KB Output is correct
16 Correct 34 ms 41440 KB Output is correct
17 Correct 30 ms 41264 KB Output is correct
18 Correct 27 ms 41304 KB Output is correct
19 Correct 29 ms 41468 KB Output is correct
20 Correct 28 ms 41408 KB Output is correct
21 Correct 30 ms 41556 KB Output is correct
22 Correct 28 ms 41576 KB Output is correct
23 Correct 30 ms 41528 KB Output is correct
24 Correct 32 ms 42404 KB Output is correct
25 Correct 30 ms 41700 KB Output is correct
26 Correct 43 ms 42320 KB Output is correct
27 Correct 33 ms 42292 KB Output is correct
28 Correct 29 ms 41812 KB Output is correct
29 Correct 29 ms 41696 KB Output is correct
30 Correct 43 ms 42116 KB Output is correct
31 Correct 30 ms 42240 KB Output is correct
32 Correct 33 ms 41896 KB Output is correct
33 Correct 27 ms 41300 KB Output is correct
34 Correct 28 ms 41256 KB Output is correct
35 Correct 33 ms 42392 KB Output is correct
36 Correct 40 ms 41816 KB Output is correct
37 Correct 29 ms 41820 KB Output is correct
38 Correct 30 ms 41820 KB Output is correct
39 Correct 35 ms 42360 KB Output is correct
40 Correct 1399 ms 205796 KB Output is correct
41 Correct 429 ms 70908 KB Output is correct
42 Correct 799 ms 128836 KB Output is correct
43 Correct 882 ms 154044 KB Output is correct
44 Correct 219 ms 65716 KB Output is correct
45 Correct 301 ms 73260 KB Output is correct
46 Correct 202 ms 67600 KB Output is correct
47 Correct 591 ms 131728 KB Output is correct
48 Correct 308 ms 97180 KB Output is correct