Submission #1288119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288119		denislav	Passport (JOI23_passport)	C++20	48 / 100	27 ms	5764 KiB

passport

# include <iostream>
# include <vector>
# include <algorithm>
# include <queue>
using namespace std;

const int MAX=2e5+11,INF=1e9;

int n,q;
pair<int,int> a[MAX];

int rep[MAX];
vector<pair<int,int>> adj[MAX*5];
void add_edge(int u, int v, int w)
{
    adj[v].push_back({u,w});
}

void build(int v=1, int l=1, int r=n)
{
    if(l==r)
    {
        rep[l]=n+v;
        add_edge(n+v,l,1);
        return ;
    }

    int mid=(l+r)/2;
    add_edge(n+v,n+v*2,0);
    add_edge(n+v,n+v*2+1,0);
    build(v*2,l,mid);
    build(v*2+1,mid+1,r);
}

void add(int le, int ri, int pos, int v=1, int l=1, int r=n)
{
    if(ri<l or r<le) return ;
    if(le<=l and r<=ri)
    {
        add_edge(pos,n+v,0);
        return ;
    }

    int mid=(l+r)/2;
    add(le,ri,pos,v*2,l,mid);
    add(le,ri,pos,v*2+1,mid+1,r);
}

int dist[MAX];
int toL[MAX];
int toR[MAX];
void bfs01(int start)
{
    for(int i=1;i<=n*5;i++)
    {
        dist[i]=INF;
        adj[i].clear();
    }

    build();
    for(int i=1;i<=n;i++)
    {
        add(a[i].first,a[i].second,i);
    }

    dist[rep[start]]=0;
    deque<pair<int,int>> dq;
    dq.push_front({rep[start],0});
    while(dq.size()>0)
    {
        int curr,d;
        tie(curr,d)=dq.front();
        dq.pop_front();
        if(d>dist[curr]) continue;

        for(pair<int,int> nxt: adj[curr])
        {
            if(dist[nxt.first]>d+nxt.second)
            {
                dist[nxt.first]=d+nxt.second;
                if(nxt.second==0) dq.push_front({nxt.first,dist[nxt.first]});
                else dq.push_back({nxt.first,dist[nxt.first]});
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(start==1) toL[i]=dist[i];
        else toR[i]=dist[i];
    }
}

int out[MAX];
void dijkstra()
{
    for(int i=0;i<=n*5;i++)
    {
        dist[i]=INF;
        adj[i].clear();
    }

    build();
    for(int i=1;i<=n;i++)
    {
        add(a[i].first,a[i].second,i);
        if(toL[i]!=INF and toR[i]!=INF) add_edge(i,0,toL[i]+toR[i]);
    }

    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    dist[0]=0;
    pq.push({0,0});
    while(pq.size()>0)
    {
        int curr,d;
        tie(d,curr)=pq.top();
        pq.pop();
        if(d>dist[curr]) continue;

        for(pair<int,int> nxt: adj[curr])
        {
            if(dist[nxt.first]>d+nxt.second)
            {
                dist[nxt.first]=d+nxt.second;
                pq.push({dist[nxt.first],nxt.first});
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(dist[i]==INF) out[i]=-1;
        else out[i]=dist[i]+1;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second;

    bfs01(1);
    bfs01(n);
    dijkstra();

    //for(int i=1;i<=n;i++) cout<<i<<":"<<toL[i]<<" "<<toR[i]<<"\n";

    cin>>q;
    while(q--)
    {
        int x;
        cin>>x;
        if(out[x]==INF) cout<<-1<<"\n";
        else cout<<out[x]<<"\n";
    }

    return 0;
}

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