oj.uz

Submission #956567

# Submission time Handle Problem Language Result Execution time Memory
956567 2024-04-02T07:17:12 Z ZHIRDILBILDIZ Passport (JOI23_passport) C++14
100 / 100
 1686 ms 187596 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long

using namespace std;
const ll N = (1 << 18);
const ll inf = 1e9;

ll n;
ll dist[3 * N + 10];
vector<pair<ll, ll>> 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 (ll l1, ll r1, ll city, ll l = 1, ll r = N, ll v = 1) {
    if (l > r1 || r < l1)
        return;
    if (l1 <= l && r <= r1) {
        gr[v + N].push_back({city, 1});
        return;
    }
    ll mid = (l + r) >> 1;
    add (l1, r1, city, l, mid, v << 1);
    add (l1, r1, city, mid + 1, r, v << 1 ^ 1);
}

vector<ll> deikstra (vector<pair<ll, ll>> v) {
    vector<ll> dist(3 * N + 1, inf);
    for (auto i : v)
        dist[i.fi] = i.se;
    set<pair<ll, ll>> st;
    for (ll i = 0; i < dist.size(); ++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] > dist[p.se] + i.se) {
                st.erase({dist[i.fi], i.fi});
                dist[i.fi] = dist[p.se] + 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 (l, r, i);
    }

    vector<ll> dist_from_one = deikstra({{1, 0}});
    vector<ll> dist_from_n = deikstra({{n, 0}});

    vector<pair<ll, ll>> 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);

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

Compilation message

passport.cpp: In function 'std::vector<long long int> deikstra(std::vector<std::pair<long long int, long long int> >)':
passport.cpp:43:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (ll i = 0; i < dist.size(); ++i)
      |                    ~~^~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 99096 KB Output is correct
2 Correct 577 ms 99156 KB Output is correct
3 Correct 579 ms 99104 KB Output is correct
4 Correct 1530 ms 168444 KB Output is correct
5 Correct 1116 ms 130900 KB Output is correct
6 Correct 906 ms 120756 KB Output is correct
7 Correct 1010 ms 147868 KB Output is correct
8 Correct 786 ms 146268 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 99128 KB Output is correct
2 Correct 570 ms 99100 KB Output is correct
3 Correct 546 ms 99104 KB Output is correct
4 Correct 548 ms 99164 KB Output is correct
5 Correct 545 ms 99080 KB Output is correct
6 Correct 590 ms 99320 KB Output is correct
7 Correct 586 ms 99200 KB Output is correct
8 Correct 566 ms 99108 KB Output is correct
9 Correct 558 ms 99104 KB Output is correct
10 Correct 541 ms 99136 KB Output is correct
11 Correct 579 ms 99144 KB Output is correct
12 Correct 581 ms 99072 KB Output is correct
13 Correct 604 ms 99152 KB Output is correct
14 Correct 575 ms 99160 KB Output is correct
15 Correct 563 ms 99124 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 99128 KB Output is correct
2 Correct 570 ms 99100 KB Output is correct
3 Correct 546 ms 99104 KB Output is correct
4 Correct 548 ms 99164 KB Output is correct
5 Correct 545 ms 99080 KB Output is correct
6 Correct 590 ms 99320 KB Output is correct
7 Correct 586 ms 99200 KB Output is correct
8 Correct 566 ms 99108 KB Output is correct
9 Correct 558 ms 99104 KB Output is correct
10 Correct 541 ms 99136 KB Output is correct
11 Correct 579 ms 99144 KB Output is correct
12 Correct 581 ms 99072 KB Output is correct
13 Correct 604 ms 99152 KB Output is correct
14 Correct 575 ms 99160 KB Output is correct
15 Correct 563 ms 99124 KB Output is correct
16 Correct 560 ms 99660 KB Output is correct
17 Correct 599 ms 99324 KB Output is correct
18 Correct 591 ms 99808 KB Output is correct
19 Correct 580 ms 99756 KB Output is correct
20 Correct 577 ms 99484 KB Output is correct
21 Correct 569 ms 99516 KB Output is correct
22 Correct 557 ms 99540 KB Output is correct
23 Correct 571 ms 99520 KB Output is correct
24 Correct 565 ms 99620 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 99128 KB Output is correct
2 Correct 570 ms 99100 KB Output is correct
3 Correct 546 ms 99104 KB Output is correct
4 Correct 548 ms 99164 KB Output is correct
5 Correct 545 ms 99080 KB Output is correct
6 Correct 590 ms 99320 KB Output is correct
7 Correct 586 ms 99200 KB Output is correct
8 Correct 566 ms 99108 KB Output is correct
9 Correct 558 ms 99104 KB Output is correct
10 Correct 541 ms 99136 KB Output is correct
11 Correct 579 ms 99144 KB Output is correct
12 Correct 581 ms 99072 KB Output is correct
13 Correct 604 ms 99152 KB Output is correct
14 Correct 575 ms 99160 KB Output is correct
15 Correct 563 ms 99124 KB Output is correct
16 Correct 560 ms 99660 KB Output is correct
17 Correct 599 ms 99324 KB Output is correct
18 Correct 591 ms 99808 KB Output is correct
19 Correct 580 ms 99756 KB Output is correct
20 Correct 577 ms 99484 KB Output is correct
21 Correct 569 ms 99516 KB Output is correct
22 Correct 557 ms 99540 KB Output is correct
23 Correct 571 ms 99520 KB Output is correct
24 Correct 565 ms 99620 KB Output is correct
25 Correct 597 ms 99192 KB Output is correct
26 Correct 594 ms 99112 KB Output is correct
27 Correct 592 ms 99596 KB Output is correct
28 Correct 570 ms 99336 KB Output is correct
29 Correct 587 ms 99512 KB Output is correct
30 Correct 554 ms 99332 KB Output is correct
31 Correct 588 ms 99508 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 99096 KB Output is correct
2 Correct 577 ms 99156 KB Output is correct
3 Correct 579 ms 99104 KB Output is correct
4 Correct 1530 ms 168444 KB Output is correct
5 Correct 1116 ms 130900 KB Output is correct
6 Correct 906 ms 120756 KB Output is correct
7 Correct 1010 ms 147868 KB Output is correct
8 Correct 786 ms 146268 KB Output is correct
9 Correct 560 ms 99128 KB Output is correct
10 Correct 570 ms 99100 KB Output is correct
11 Correct 546 ms 99104 KB Output is correct
12 Correct 548 ms 99164 KB Output is correct
13 Correct 545 ms 99080 KB Output is correct
14 Correct 590 ms 99320 KB Output is correct
15 Correct 586 ms 99200 KB Output is correct
16 Correct 566 ms 99108 KB Output is correct
17 Correct 558 ms 99104 KB Output is correct
18 Correct 541 ms 99136 KB Output is correct
19 Correct 579 ms 99144 KB Output is correct
20 Correct 581 ms 99072 KB Output is correct
21 Correct 604 ms 99152 KB Output is correct
22 Correct 575 ms 99160 KB Output is correct
23 Correct 563 ms 99124 KB Output is correct
24 Correct 560 ms 99660 KB Output is correct
25 Correct 599 ms 99324 KB Output is correct
26 Correct 591 ms 99808 KB Output is correct
27 Correct 580 ms 99756 KB Output is correct
28 Correct 577 ms 99484 KB Output is correct
29 Correct 569 ms 99516 KB Output is correct
30 Correct 557 ms 99540 KB Output is correct
31 Correct 571 ms 99520 KB Output is correct
32 Correct 565 ms 99620 KB Output is correct
33 Correct 597 ms 99192 KB Output is correct
34 Correct 594 ms 99112 KB Output is correct
35 Correct 592 ms 99596 KB Output is correct
36 Correct 570 ms 99336 KB Output is correct
37 Correct 587 ms 99512 KB Output is correct
38 Correct 554 ms 99332 KB Output is correct
39 Correct 588 ms 99508 KB Output is correct
40 Correct 1686 ms 170272 KB Output is correct
41 Correct 1124 ms 133368 KB Output is correct
42 Correct 1312 ms 186820 KB Output is correct
43 Correct 1201 ms 187596 KB Output is correct
44 Correct 950 ms 120772 KB Output is correct
45 Correct 1026 ms 136764 KB Output is correct
46 Correct 856 ms 113756 KB Output is correct
47 Correct 1347 ms 146048 KB Output is correct
48 Correct 1105 ms 152936 KB Output is correct