Submission #1018198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018198		alexdd	Passport (JOI23_passport)	C++17	100 / 100	594 ms	132572 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;
    priority_queue<pair<int,int>> pq;
    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;
        }
        pq.push({-rez[id[i]],id[i]});
    }
    while(!pq.empty())
    {
        int nod = pq.top().second;
        int cdist = -pq.top().first;
        pq.pop();
        if(rez[nod]!=cdist)
            continue;
        for(auto [adj,c]:conrev[nod])
        {
            if(rez[adj]>rez[nod]+c)
            {
                rez[adj] = rez[nod]+c;
                pq.push({-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);
    //for(int i=1;i<=n;i++) cout<<i<<"  "<<dist1[id[i]]<<" "<<distn[id[i]]<<"  dist1 & distn\n";
    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: 46 / 46