Submission #895682

#	Time	Username	Problem	Language	Result	Execution time	Memory
895682		Tuanlinh123	Passport (JOI23_passport)	C++17	0 / 100	579 ms	86064 KiB

passport

#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({i, le[i]+ri[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: 0 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46