제출 #1155720

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155720		abcdxyz123	Passport (JOI23_passport)	C++17	100 / 100	338 ms	81628 KiB

passport

#include<bits/stdc++.h>
#define maxn 200005
#define inf 1000000000
#define pi pair<int,int>
#define fi first
#define se second
using namespace std;
int n,Q;
int l[maxn];
int r[maxn];
int p[maxn];
vector<pi>adj[4*maxn];
void build(int r=1,int lo=1,int hi=n)
{
    if(lo==hi)
    {
        p[lo]=r;
        return;
    }
    int mid=(lo+hi)/2;
    build(2*r,lo,mid);
    build(2*r+1,mid+1,hi);
    adj[2*r].push_back({r,0});
    adj[2*r+1].push_back({r,0});
}
void Link(int x,int u,int v,int r=1,int lo=1,int hi=n)
{
    if(u>hi||v<lo)return;
    if(u<=lo&&hi<=v)
    {
        adj[r].push_back({p[x],1});
        return;
    }
    int mid=(lo+hi)/2;
    Link(x,u,v,2*r,lo,mid);
    Link(x,u,v,2*r+1,mid+1,hi);
}
int ds[4*maxn];
int dt[4*maxn];
void Dijkstra(int s,int d[])
{
    for(int i=1;i<=4*n;i++)
    {
        d[i]=inf;
    }
    d[s]=0;
    deque<int>q;
    q.push_front(s);
    while(!q.empty())
    {
        int u=q.front();
        q.pop_front();
        for(auto[v,w]:adj[u])
        {
            if(d[v]==inf)
            {
                d[v]=d[u]+w;
                if(w)q.push_back(v);
                else q.push_front(v);
            }
        }
    }
}
int d[4*maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>l[i]>>r[i];
    }
    build();
    for(int i=1;i<=n;i++)
    {
        Link(i,l[i],r[i]);
    }
    Dijkstra(p[1],ds);
    Dijkstra(p[n],dt);
    for(int i=1;i<=4*n;i++)
    {
        d[i]=inf;
    }
    priority_queue<pi,vector<pi>,greater<pi>>q;
    cout<<'\n';
    for(int i=1;i<=4*n;i++)
    {
        //cout<<ds[i]<<' '<<dt[i]<<'\n';
    }
    for(int i=1;i<=n;i++)
    {

        if(i==1||i==n)d[p[i]]=ds[p[i]]+dt[p[i]];
        else d[p[i]]=ds[p[i]]+dt[p[i]]-1;
        //cout<<i<<' '<<d[p[i]]<<'\n';
        q.push({d[p[i]],p[i]});
    }
    while(!q.empty())
    {
        int cur=q.top().fi;
        int u=q.top().se;
        q.pop();
        if(d[u]!=cur)continue;
        for(auto[v,w]:adj[u])
        {
            if(d[v]>d[u]+w)
            {
                d[v]=d[u]+w;
                q.push({d[v],v});
            }
        }
    }
    cin>>Q;
    while(Q--)
    {
        int x;
        cin>>x;
        if(d[p[x]]>=inf)cout<<-1<<'\n';
        else cout<<d[p[x]]<<'\n';
    }

}

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