Submission #1018202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018202		alexdd	Passport (JOI23_passport)	C++17	54 / 100	2056 ms	129360 KiB

passport

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n,cntn;
vector<pair<int,int>> con[530005];
vector<pair<int,int>> conrev[530005];
int id[200005];
void build(int nod, int st, int dr)
{
    cntn = max(cntn, nod);
    if(st==dr)
    {
        id[st]=nod;
        return;
    }
    con[nod].push_back({nod*2,0});
    con[nod].push_back({nod*2+1,0});
    conrev[nod*2].push_back({nod,0});
    conrev[nod*2+1].push_back({nod,0});
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
}
void baga(int nod, int st, int dr, int le, int ri, int from)
{
    if(le>ri)
        return;
    if(le==st && dr==ri)
    {
        con[from].push_back({nod,1});
        conrev[nod].push_back({from,1});
        return;
    }
    int mij=(st+dr)/2;
    baga(nod*2,st,mij,le,min(mij,ri),from);
    baga(nod*2+1,mij+1,dr,max(mij+1,le),ri,from);
}
void bfs(int src, int dist[])
{
    for(int i=1;i<=cntn;i++)
        dist[i]=INF;
    deque<int> dq;
    dist[src]=0;
    dq.push_back(src);
    while(!dq.empty())
    {
        int nod = dq.front();
        dq.pop_front();
        for(auto [adj,c]:conrev[nod])
        {
            if(dist[adj] > dist[nod]+c)
            {
                dist[adj] = dist[nod]+c;
                if(c==1) dq.push_back(adj);
                else dq.push_front(adj);
            }
        }
    }
}
int dist1[530000],distn[530000],rez[530000];
void dijkstra()
{
    for(int i=1;i<=cntn;i++)
        rez[i]=INF;
    deque<pair<int,int>> dq;
    for(int i=1;i<=n;i++)
    {
        if(i==1) rez[id[i]] = distn[id[i]];
        else if(i==n) rez[id[i]] = dist1[id[i]];
        else if(dist1[id[i]]==1 && distn[id[i]]==1) rez[id[i]] = 1;
        else if(dist1[id[i]]==1) rez[id[i]] = distn[id[i]];
        else if(distn[id[i]]==1) rez[id[i]] = dist1[id[i]];
        else rez[id[i]] = dist1[id[i]] + distn[id[i]] - 1;
        dq.push_back({rez[id[i]],id[i]});
    }
    sort(dq.begin(),dq.end());
    while(!dq.empty())
    {
        int nod = dq.front().second;
        int cdist = dq.front().first;
        dq.pop_front();
        if(rez[nod]!=cdist)
            continue;
        for(auto [adj,c]:conrev[nod])
        {
            if(rez[adj]>rez[nod]+c)
            {
                rez[adj] = rez[nod]+c;
                if(c==0) dq.push_front({rez[adj],adj});
                else dq.push_back({rez[adj],adj});
            }
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    build(1,1,n);
    int le,ri;
    for(int i=1;i<=n;i++)
    {
        cin>>le>>ri;
        baga(1,1,n,le,ri,id[i]);
    }
    bfs(id[1],dist1);
    bfs(id[n],distn);
    dijkstra();
    int q,a;
    cin>>q;
    while(q--)
    {
        cin>>a;
        if(rez[id[a]]<=n+5) cout<<rez[id[a]]<<"\n";
        else cout<<-1<<"\n";
    }
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 0 / 46