oj.uz

Submission #895685

# Submission time Handle Problem Language Result Execution time Memory
895685 2023-12-30T14:08:25 Z Tuanlinh123 Passport (JOI23_passport) C++17
100 / 100
 577 ms 94888 KB 
#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

const ll maxn=200005, inf=1e9;
vector <pll> A[maxn*4];
priority_queue <pll, vector <pll>, greater<pll>> q, q1, q2;
ll le[maxn*4], ri[maxn*4], L[maxn*4], R[maxn*4], dis[maxn*4], idx[maxn*4];

void build(ll i, ll Start, ll End)
{
    le[i]=ri[i]=dis[i]=inf;
    if (Start==End)
    {
        idx[Start]=i;
        return;
    }
    ll mid=(Start+End)/2;
    build(i*2, Start, mid);
    build(i*2+1, mid+1, End);
    A[i*2].pb({i, 0}); A[i*2+1].pb({i, 0});
}

void push(ll i, ll Start, ll End, ll l, ll r, ll p)
{
    if (Start>r || End<l)
        return;
    if (Start>=l && End<=r)
    {
        A[i].pb({idx[p], 1});
        return;
    }
    ll mid=(Start+End)/2;
    if (mid>=l) push(i*2, Start, mid, l, r, p);
    if (mid+1<=r) push(i*2+1, mid+1, End, l, r, p);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n; cin >> n;
    for (ll i=1; i<=n; i++)
        cin >> L[i] >> R[i];
    build(1, 1, n);
    for (ll i=1; i<=n; i++)
        push(1, 1, n, L[i], R[i], i);
    for (ll i=1; i<=n; i++)
    {
        ll id=idx[i];
        if (L[i]==1) le[id]=0, q1.push({0, id});
        if (R[i]==n) ri[id]=0, q2.push({0, id});
    }
    while (q1.size())
    {
        ll u=q1.top().se, leu=q1.top().fi; q1.pop();
        if (leu!=le[u]) continue;
        for (pll child:A[u])
        {
            ll v=child.fi, w=child.se;
            if (le[v]>leu+w)
                le[v]=leu+w, q1.push({le[v], v});
        }
    }
    while (q2.size())
    {
        ll u=q2.top().se, riu=q2.top().fi; q2.pop();
        if (riu!=ri[u]) continue;
        for (pll child:A[u])
        {
            ll v=child.fi, w=child.se;
            if (ri[v]>riu+w)
                ri[v]=riu+w, q2.push({ri[v], v});
        }
    }
    for (ll i=1; i<=n; i++)
        A[0].pb({idx[i], le[idx[i]]+ri[idx[i]]});
    q.push({1, 0}); dis[0]=1;
    while (q.size())
    {
        ll u=q.top().se, disu=q.top().fi; q.pop();
        if (disu!=dis[u]) continue;
        for (pll child:A[u])
        {
            ll v=child.fi, w=child.se;
            if (dis[v]>disu+w)
                dis[v]=disu+w, q.push({dis[v], v});
        }
    }
    ll q; cin >> q;
    for (ll i=1; i<=q; i++)
    {
        ll x; cin >> x;
        if (dis[idx[x]]>=inf) cout << "-1\n";
        else cout << dis[idx[x]] << "\n";
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29532 KB Output is correct
2 Correct 5 ms 29532 KB Output is correct
3 Correct 5 ms 29532 KB Output is correct
4 Correct 555 ms 83808 KB Output is correct
5 Correct 251 ms 61248 KB Output is correct
6 Correct 145 ms 56008 KB Output is correct
7 Correct 175 ms 57860 KB Output is correct
8 Correct 113 ms 62132 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29532 KB Output is correct
2 Correct 6 ms 29620 KB Output is correct
3 Correct 5 ms 29532 KB Output is correct
4 Correct 6 ms 29532 KB Output is correct
5 Correct 5 ms 29532 KB Output is correct
6 Correct 5 ms 29528 KB Output is correct
7 Correct 5 ms 29532 KB Output is correct
8 Correct 6 ms 29532 KB Output is correct
9 Correct 5 ms 29624 KB Output is correct
10 Correct 5 ms 29532 KB Output is correct
11 Correct 6 ms 29532 KB Output is correct
12 Correct 6 ms 29532 KB Output is correct
13 Correct 6 ms 29720 KB Output is correct
14 Correct 6 ms 29532 KB Output is correct
15 Correct 6 ms 29532 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29532 KB Output is correct
2 Correct 6 ms 29620 KB Output is correct
3 Correct 5 ms 29532 KB Output is correct
4 Correct 6 ms 29532 KB Output is correct
5 Correct 5 ms 29532 KB Output is correct
6 Correct 5 ms 29528 KB Output is correct
7 Correct 5 ms 29532 KB Output is correct
8 Correct 6 ms 29532 KB Output is correct
9 Correct 5 ms 29624 KB Output is correct
10 Correct 5 ms 29532 KB Output is correct
11 Correct 6 ms 29532 KB Output is correct
12 Correct 6 ms 29532 KB Output is correct
13 Correct 6 ms 29720 KB Output is correct
14 Correct 6 ms 29532 KB Output is correct
15 Correct 6 ms 29532 KB Output is correct
16 Correct 9 ms 30116 KB Output is correct
17 Correct 8 ms 29788 KB Output is correct
18 Correct 9 ms 30044 KB Output is correct
19 Correct 8 ms 30040 KB Output is correct
20 Correct 7 ms 29788 KB Output is correct
21 Correct 7 ms 29788 KB Output is correct
22 Correct 6 ms 29788 KB Output is correct
23 Correct 8 ms 29896 KB Output is correct
24 Correct 7 ms 30044 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29532 KB Output is correct
2 Correct 6 ms 29620 KB Output is correct
3 Correct 5 ms 29532 KB Output is correct
4 Correct 6 ms 29532 KB Output is correct
5 Correct 5 ms 29532 KB Output is correct
6 Correct 5 ms 29528 KB Output is correct
7 Correct 5 ms 29532 KB Output is correct
8 Correct 6 ms 29532 KB Output is correct
9 Correct 5 ms 29624 KB Output is correct
10 Correct 5 ms 29532 KB Output is correct
11 Correct 6 ms 29532 KB Output is correct
12 Correct 6 ms 29532 KB Output is correct
13 Correct 6 ms 29720 KB Output is correct
14 Correct 6 ms 29532 KB Output is correct
15 Correct 6 ms 29532 KB Output is correct
16 Correct 9 ms 30116 KB Output is correct
17 Correct 8 ms 29788 KB Output is correct
18 Correct 9 ms 30044 KB Output is correct
19 Correct 8 ms 30040 KB Output is correct
20 Correct 7 ms 29788 KB Output is correct
21 Correct 7 ms 29788 KB Output is correct
22 Correct 6 ms 29788 KB Output is correct
23 Correct 8 ms 29896 KB Output is correct
24 Correct 7 ms 30044 KB Output is correct
25 Correct 6 ms 29532 KB Output is correct
26 Correct 5 ms 29496 KB Output is correct
27 Correct 9 ms 30044 KB Output is correct
28 Correct 9 ms 29788 KB Output is correct
29 Correct 7 ms 29828 KB Output is correct
30 Correct 7 ms 29788 KB Output is correct
31 Correct 9 ms 29788 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29532 KB Output is correct
2 Correct 5 ms 29532 KB Output is correct
3 Correct 5 ms 29532 KB Output is correct
4 Correct 555 ms 83808 KB Output is correct
5 Correct 251 ms 61248 KB Output is correct
6 Correct 145 ms 56008 KB Output is correct
7 Correct 175 ms 57860 KB Output is correct
8 Correct 113 ms 62132 KB Output is correct
9 Correct 6 ms 29532 KB Output is correct
10 Correct 6 ms 29620 KB Output is correct
11 Correct 5 ms 29532 KB Output is correct
12 Correct 6 ms 29532 KB Output is correct
13 Correct 5 ms 29532 KB Output is correct
14 Correct 5 ms 29528 KB Output is correct
15 Correct 5 ms 29532 KB Output is correct
16 Correct 6 ms 29532 KB Output is correct
17 Correct 5 ms 29624 KB Output is correct
18 Correct 5 ms 29532 KB Output is correct
19 Correct 6 ms 29532 KB Output is correct
20 Correct 6 ms 29532 KB Output is correct
21 Correct 6 ms 29720 KB Output is correct
22 Correct 6 ms 29532 KB Output is correct
23 Correct 6 ms 29532 KB Output is correct
24 Correct 9 ms 30116 KB Output is correct
25 Correct 8 ms 29788 KB Output is correct
26 Correct 9 ms 30044 KB Output is correct
27 Correct 8 ms 30040 KB Output is correct
28 Correct 7 ms 29788 KB Output is correct
29 Correct 7 ms 29788 KB Output is correct
30 Correct 6 ms 29788 KB Output is correct
31 Correct 8 ms 29896 KB Output is correct
32 Correct 7 ms 30044 KB Output is correct
33 Correct 6 ms 29532 KB Output is correct
34 Correct 5 ms 29496 KB Output is correct
35 Correct 9 ms 30044 KB Output is correct
36 Correct 9 ms 29788 KB Output is correct
37 Correct 7 ms 29828 KB Output is correct
38 Correct 7 ms 29788 KB Output is correct
39 Correct 9 ms 29788 KB Output is correct
40 Correct 577 ms 88732 KB Output is correct
41 Correct 276 ms 65080 KB Output is correct
42 Correct 365 ms 92268 KB Output is correct
43 Correct 365 ms 94888 KB Output is correct
44 Correct 178 ms 59972 KB Output is correct
45 Correct 187 ms 67248 KB Output is correct
46 Correct 113 ms 47108 KB Output is correct
47 Correct 357 ms 69160 KB Output is correct
48 Correct 239 ms 76700 KB Output is correct