oj.uz

Submission #956603

# Submission time Handle Problem Language Result Execution time Memory
956603 2024-04-02T08:18:22 Z ZHIRDILBILDIZ Passport (JOI23_passport) C++14
100 / 100
 1619 ms 184324 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 = 1; 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 555 ms 98920 KB Output is correct
2 Correct 549 ms 99144 KB Output is correct
3 Correct 554 ms 99016 KB Output is correct
4 Correct 1569 ms 165812 KB Output is correct
5 Correct 1108 ms 128040 KB Output is correct
6 Correct 1025 ms 118264 KB Output is correct
7 Correct 1090 ms 145572 KB Output is correct
8 Correct 813 ms 144384 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 98920 KB Output is correct
2 Correct 587 ms 98896 KB Output is correct
3 Correct 553 ms 99060 KB Output is correct
4 Correct 560 ms 98904 KB Output is correct
5 Correct 542 ms 98900 KB Output is correct
6 Correct 556 ms 99164 KB Output is correct
7 Correct 564 ms 99164 KB Output is correct
8 Correct 544 ms 98900 KB Output is correct
9 Correct 548 ms 98896 KB Output is correct
10 Correct 551 ms 98920 KB Output is correct
11 Correct 545 ms 98812 KB Output is correct
12 Correct 573 ms 98900 KB Output is correct
13 Correct 552 ms 99080 KB Output is correct
14 Correct 563 ms 98952 KB Output is correct
15 Correct 556 ms 98896 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 98920 KB Output is correct
2 Correct 587 ms 98896 KB Output is correct
3 Correct 553 ms 99060 KB Output is correct
4 Correct 560 ms 98904 KB Output is correct
5 Correct 542 ms 98900 KB Output is correct
6 Correct 556 ms 99164 KB Output is correct
7 Correct 564 ms 99164 KB Output is correct
8 Correct 544 ms 98900 KB Output is correct
9 Correct 548 ms 98896 KB Output is correct
10 Correct 551 ms 98920 KB Output is correct
11 Correct 545 ms 98812 KB Output is correct
12 Correct 573 ms 98900 KB Output is correct
13 Correct 552 ms 99080 KB Output is correct
14 Correct 563 ms 98952 KB Output is correct
15 Correct 556 ms 98896 KB Output is correct
16 Correct 559 ms 99420 KB Output is correct
17 Correct 581 ms 99232 KB Output is correct
18 Correct 569 ms 99728 KB Output is correct
19 Correct 569 ms 99816 KB Output is correct
20 Correct 584 ms 99732 KB Output is correct
21 Correct 549 ms 99160 KB Output is correct
22 Correct 551 ms 99236 KB Output is correct
23 Correct 559 ms 99392 KB Output is correct
24 Correct 568 ms 99228 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 98920 KB Output is correct
2 Correct 587 ms 98896 KB Output is correct
3 Correct 553 ms 99060 KB Output is correct
4 Correct 560 ms 98904 KB Output is correct
5 Correct 542 ms 98900 KB Output is correct
6 Correct 556 ms 99164 KB Output is correct
7 Correct 564 ms 99164 KB Output is correct
8 Correct 544 ms 98900 KB Output is correct
9 Correct 548 ms 98896 KB Output is correct
10 Correct 551 ms 98920 KB Output is correct
11 Correct 545 ms 98812 KB Output is correct
12 Correct 573 ms 98900 KB Output is correct
13 Correct 552 ms 99080 KB Output is correct
14 Correct 563 ms 98952 KB Output is correct
15 Correct 556 ms 98896 KB Output is correct
16 Correct 559 ms 99420 KB Output is correct
17 Correct 581 ms 99232 KB Output is correct
18 Correct 569 ms 99728 KB Output is correct
19 Correct 569 ms 99816 KB Output is correct
20 Correct 584 ms 99732 KB Output is correct
21 Correct 549 ms 99160 KB Output is correct
22 Correct 551 ms 99236 KB Output is correct
23 Correct 559 ms 99392 KB Output is correct
24 Correct 568 ms 99228 KB Output is correct
25 Correct 545 ms 98900 KB Output is correct
26 Correct 555 ms 98908 KB Output is correct
27 Correct 596 ms 99488 KB Output is correct
28 Correct 561 ms 99232 KB Output is correct
29 Correct 605 ms 99236 KB Output is correct
30 Correct 559 ms 99228 KB Output is correct
31 Correct 584 ms 99276 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 98920 KB Output is correct
2 Correct 549 ms 99144 KB Output is correct
3 Correct 554 ms 99016 KB Output is correct
4 Correct 1569 ms 165812 KB Output is correct
5 Correct 1108 ms 128040 KB Output is correct
6 Correct 1025 ms 118264 KB Output is correct
7 Correct 1090 ms 145572 KB Output is correct
8 Correct 813 ms 144384 KB Output is correct
9 Correct 560 ms 98920 KB Output is correct
10 Correct 587 ms 98896 KB Output is correct
11 Correct 553 ms 99060 KB Output is correct
12 Correct 560 ms 98904 KB Output is correct
13 Correct 542 ms 98900 KB Output is correct
14 Correct 556 ms 99164 KB Output is correct
15 Correct 564 ms 99164 KB Output is correct
16 Correct 544 ms 98900 KB Output is correct
17 Correct 548 ms 98896 KB Output is correct
18 Correct 551 ms 98920 KB Output is correct
19 Correct 545 ms 98812 KB Output is correct
20 Correct 573 ms 98900 KB Output is correct
21 Correct 552 ms 99080 KB Output is correct
22 Correct 563 ms 98952 KB Output is correct
23 Correct 556 ms 98896 KB Output is correct
24 Correct 559 ms 99420 KB Output is correct
25 Correct 581 ms 99232 KB Output is correct
26 Correct 569 ms 99728 KB Output is correct
27 Correct 569 ms 99816 KB Output is correct
28 Correct 584 ms 99732 KB Output is correct
29 Correct 549 ms 99160 KB Output is correct
30 Correct 551 ms 99236 KB Output is correct
31 Correct 559 ms 99392 KB Output is correct
32 Correct 568 ms 99228 KB Output is correct
33 Correct 545 ms 98900 KB Output is correct
34 Correct 555 ms 98908 KB Output is correct
35 Correct 596 ms 99488 KB Output is correct
36 Correct 561 ms 99232 KB Output is correct
37 Correct 605 ms 99236 KB Output is correct
38 Correct 559 ms 99228 KB Output is correct
39 Correct 584 ms 99276 KB Output is correct
40 Correct 1619 ms 166452 KB Output is correct
41 Correct 1142 ms 129252 KB Output is correct
42 Correct 1285 ms 183060 KB Output is correct
43 Correct 1192 ms 184324 KB Output is correct
44 Correct 986 ms 117952 KB Output is correct
45 Correct 1066 ms 132476 KB Output is correct
46 Correct 910 ms 112280 KB Output is correct
47 Correct 1348 ms 143096 KB Output is correct
48 Correct 1051 ms 148916 KB Output is correct