oj.uz

Submission #956602

# Submission time Handle Problem Language Result Execution time Memory
956602 2024-04-02T08:17:45 Z ZHIRDILBILDIZ Passport (JOI23_passport) C++14
100 / 100
 1664 ms 184780 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pll pair<ll, ll>
using namespace std;
const ll N = (1 << 18);
const ll INF = 1e18;
ll n, q;
vector<pll> gr[3 * N + 10];
void build (ll l = 1, ll r = N, ll v = 1) {
    if (l == r) {
        gr[l].push_back({v + N, 0});
        return;
    }
    ll mid = (l + r) >> 1;
    build(l, mid, v << 1);
    build(mid + 1, r, v << 1 ^ 1);
    gr[(v << 1) + N].push_back({v + N, 0});
    gr[((v << 1) ^ 1) + N].push_back({v + N, 0});
}
void add_road (ll l1, ll r1, ll x, ll v = 1, ll l = 1, ll r = N) {
    if (l > r1 || r < l1)
        return;
    if (l1 <= l && r <= r1) {
        gr[v + N].push_back({x, 1});
        return;
    }
    ll mid = (l + r) >> 1;
    add_road (l1, r1, x, v << 1, l, mid);
    add_road (l1, r1, x, v << 1 ^ 1, mid + 1, r);
}

vector<ll> deikstra (vector<pll> v) {
    vector<ll> dist(3 * N, INF);
    for (auto i : v)
        dist[i.fi] = i.se;
    set<pll> st;
    for (auto i = 0; i < 3 * N; ++i)
        st.insert({dist[i], i});
    while (st.size()) {
        auto p = *st.begin();
        st.erase(st.begin());
        for (auto i : gr[p.se])
            if (dist[i.fi] > p.fi + i.se) {
                st.erase({dist[i.fi], i.fi});
                dist[i.fi] = p.fi + i.se;
                st.insert({dist[i.fi], i.fi});
            }
    }
    vector<ll> now(n + 1);
    for (ll i = 1; i <= n; ++i)
        now[i] = dist[i];
    return now;
}

signed main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    build();
    cin >> n;
    for (ll i = 1; i <= n; ++i) {
        ll l, r;
        cin >> l >> r;
        add_road (l, r, i);
    }

    vector<ll> dist_from_n = deikstra({{n, 0}});
    vector<ll> dist_from_one = deikstra({{1, 0}});
    vector<pll> v;
    for (ll i = 1; i <= n; ++i)
        v.push_back({i, dist_from_n[i] + dist_from_one[i] - (1 < i && i < n)});
    vector<ll> ans = deikstra(v);

    cin >> q;
    while (q--) {
        ll x;
        cin >> x;
        if (ans[x] >= INF)
            cout << "-1\n";
        else
            cout << ans[x] << '\n';
    }
    return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 98900 KB Output is correct
2 Correct 575 ms 99064 KB Output is correct
3 Correct 561 ms 98920 KB Output is correct
4 Correct 1664 ms 166048 KB Output is correct
5 Correct 1134 ms 128028 KB Output is correct
6 Correct 931 ms 118012 KB Output is correct
7 Correct 1057 ms 150244 KB Output is correct
8 Correct 820 ms 144304 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 99016 KB Output is correct
2 Correct 564 ms 98860 KB Output is correct
3 Correct 564 ms 98900 KB Output is correct
4 Correct 551 ms 99148 KB Output is correct
5 Correct 549 ms 98900 KB Output is correct
6 Correct 638 ms 98916 KB Output is correct
7 Correct 550 ms 98896 KB Output is correct
8 Correct 602 ms 99040 KB Output is correct
9 Correct 539 ms 98896 KB Output is correct
10 Correct 544 ms 98816 KB Output is correct
11 Correct 557 ms 98976 KB Output is correct
12 Correct 578 ms 98836 KB Output is correct
13 Correct 561 ms 98992 KB Output is correct
14 Correct 556 ms 99020 KB Output is correct
15 Correct 558 ms 98968 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 99016 KB Output is correct
2 Correct 564 ms 98860 KB Output is correct
3 Correct 564 ms 98900 KB Output is correct
4 Correct 551 ms 99148 KB Output is correct
5 Correct 549 ms 98900 KB Output is correct
6 Correct 638 ms 98916 KB Output is correct
7 Correct 550 ms 98896 KB Output is correct
8 Correct 602 ms 99040 KB Output is correct
9 Correct 539 ms 98896 KB Output is correct
10 Correct 544 ms 98816 KB Output is correct
11 Correct 557 ms 98976 KB Output is correct
12 Correct 578 ms 98836 KB Output is correct
13 Correct 561 ms 98992 KB Output is correct
14 Correct 556 ms 99020 KB Output is correct
15 Correct 558 ms 98968 KB Output is correct
16 Correct 568 ms 99228 KB Output is correct
17 Correct 571 ms 99332 KB Output is correct
18 Correct 600 ms 99964 KB Output is correct
19 Correct 566 ms 99680 KB Output is correct
20 Correct 575 ms 98976 KB Output is correct
21 Correct 543 ms 99216 KB Output is correct
22 Correct 551 ms 99732 KB Output is correct
23 Correct 560 ms 99340 KB Output is correct
24 Correct 586 ms 99196 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 99016 KB Output is correct
2 Correct 564 ms 98860 KB Output is correct
3 Correct 564 ms 98900 KB Output is correct
4 Correct 551 ms 99148 KB Output is correct
5 Correct 549 ms 98900 KB Output is correct
6 Correct 638 ms 98916 KB Output is correct
7 Correct 550 ms 98896 KB Output is correct
8 Correct 602 ms 99040 KB Output is correct
9 Correct 539 ms 98896 KB Output is correct
10 Correct 544 ms 98816 KB Output is correct
11 Correct 557 ms 98976 KB Output is correct
12 Correct 578 ms 98836 KB Output is correct
13 Correct 561 ms 98992 KB Output is correct
14 Correct 556 ms 99020 KB Output is correct
15 Correct 558 ms 98968 KB Output is correct
16 Correct 568 ms 99228 KB Output is correct
17 Correct 571 ms 99332 KB Output is correct
18 Correct 600 ms 99964 KB Output is correct
19 Correct 566 ms 99680 KB Output is correct
20 Correct 575 ms 98976 KB Output is correct
21 Correct 543 ms 99216 KB Output is correct
22 Correct 551 ms 99732 KB Output is correct
23 Correct 560 ms 99340 KB Output is correct
24 Correct 586 ms 99196 KB Output is correct
25 Correct 553 ms 98764 KB Output is correct
26 Correct 536 ms 98924 KB Output is correct
27 Correct 583 ms 99484 KB Output is correct
28 Correct 569 ms 99380 KB Output is correct
29 Correct 580 ms 99144 KB Output is correct
30 Correct 554 ms 99228 KB Output is correct
31 Correct 581 ms 99360 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 98900 KB Output is correct
2 Correct 575 ms 99064 KB Output is correct
3 Correct 561 ms 98920 KB Output is correct
4 Correct 1664 ms 166048 KB Output is correct
5 Correct 1134 ms 128028 KB Output is correct
6 Correct 931 ms 118012 KB Output is correct
7 Correct 1057 ms 150244 KB Output is correct
8 Correct 820 ms 144304 KB Output is correct
9 Correct 562 ms 99016 KB Output is correct
10 Correct 564 ms 98860 KB Output is correct
11 Correct 564 ms 98900 KB Output is correct
12 Correct 551 ms 99148 KB Output is correct
13 Correct 549 ms 98900 KB Output is correct
14 Correct 638 ms 98916 KB Output is correct
15 Correct 550 ms 98896 KB Output is correct
16 Correct 602 ms 99040 KB Output is correct
17 Correct 539 ms 98896 KB Output is correct
18 Correct 544 ms 98816 KB Output is correct
19 Correct 557 ms 98976 KB Output is correct
20 Correct 578 ms 98836 KB Output is correct
21 Correct 561 ms 98992 KB Output is correct
22 Correct 556 ms 99020 KB Output is correct
23 Correct 558 ms 98968 KB Output is correct
24 Correct 568 ms 99228 KB Output is correct
25 Correct 571 ms 99332 KB Output is correct
26 Correct 600 ms 99964 KB Output is correct
27 Correct 566 ms 99680 KB Output is correct
28 Correct 575 ms 98976 KB Output is correct
29 Correct 543 ms 99216 KB Output is correct
30 Correct 551 ms 99732 KB Output is correct
31 Correct 560 ms 99340 KB Output is correct
32 Correct 586 ms 99196 KB Output is correct
33 Correct 553 ms 98764 KB Output is correct
34 Correct 536 ms 98924 KB Output is correct
35 Correct 583 ms 99484 KB Output is correct
36 Correct 569 ms 99380 KB Output is correct
37 Correct 580 ms 99144 KB Output is correct
38 Correct 554 ms 99228 KB Output is correct
39 Correct 581 ms 99360 KB Output is correct
40 Correct 1595 ms 166760 KB Output is correct
41 Correct 1124 ms 129440 KB Output is correct
42 Correct 1269 ms 184780 KB Output is correct
43 Correct 1232 ms 182812 KB Output is correct
44 Correct 962 ms 117964 KB Output is correct
45 Correct 1010 ms 132692 KB Output is correct
46 Correct 831 ms 112028 KB Output is correct
47 Correct 1323 ms 143356 KB Output is correct
48 Correct 1060 ms 148840 KB Output is correct