Submission #888844

#	Time	Username	Problem	Language	Result	Execution time	Memory
888844		Warinchai	Passport (JOI23_passport)	C++14	100 / 100	829 ms	166276 KiB

passport

#include<bits/stdc++.h>
using namespace std;
int N=2e5;
int inf=1e6;
vector<pair<int,int> >node[1000005];
vector<pair<int,int> >rv[1000005];
int disst[1000005];
int disen[1000005];
int alldis[1000005];
int vis[1000005];
void build(int st,int en,int i,int p){
    if(st==en){
        node[p+N].push_back({st,0});
        return;
    }
    int m=(st+en)/2;
    build(st,m,i*2,i);
    build(m+1,en,i*2+1,i);
    if(p!=-1)node[p+N].push_back({i+N,0});
}
void connect(int st,int en,int i,int l,int r,int x){
    if(st>r||en<l)return;
    if(st>=l&&en<=r){
        if(st==en)return void(node[x].push_back({st,1}));
        else return void(node[x].push_back({i+N,1}));
    }
    int m=(st+en)/2;
    connect(st,m,i*2,l,r,x);
    connect(m+1,en,i*2+1,l,r,x);
}
void djikstra_st(){
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq;
    pq.push({0,1});
    for(int i=1;i<=5*N;i++)vis[i]=0;
    while(!pq.empty()){
        int x=pq.top().second;
        int c=pq.top().first;
        pq.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(auto v:rv[x])if(c+v.second<disst[v.first])pq.push({c+v.second,v.first}),disst[v.first]=c+v.second;
    }
}
void djikstra_en(){
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq;
    pq.push({0,N});
    for(int i=1;i<=5*N;i++)vis[i]=0;
    while(!pq.empty()){
        int x=pq.top().second;
        int c=pq.top().first;
        pq.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(auto v:rv[x])if(c+v.second<disen[v.first])pq.push({c+v.second,v.first}),disen[v.first]=c+v.second;
    }
}
void djikstra_all(){
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq;
    for(int i=1;i<=5*N;i++)alldis[i]=disst[i]+disen[i]-(1<i&&i<N),pq.push({alldis[i],i});
    for(int i=1;i<=5*N;i++)vis[i]=0;
    while(!pq.empty()){
        int x=pq.top().second;
        int c=pq.top().first;
        pq.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(auto v:rv[x])if(c+v.second<alldis[v.first])pq.push({c+v.second,v.first}),alldis[v.first]=c+v.second;
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>N;
    build(1,N,1,-1);
    for(int i=1;i<=N;i++){
        int a,b;
        cin>>a>>b;
        connect(1,N,1,a,b,i);
    }
    for(int i=1;i<=5*N;i++)for(auto x:node[i])rv[x.first].push_back({i,x.second});
    for(int i=1;i<=5*N;i++)disst[i]=disen[i]=alldis[i]=inf;
    disst[1]=disen[N]=0;
    djikstra_st();
    djikstra_en();
    //for(int i=1;i<=N;i++)cerr<<i<<" "<<disst[i]<<" "<<disen[i]<<endl;
    djikstra_all();
    int q;
    cin>>q;
    while(q--){
        int x;
        cin>>x;
        cout<<(alldis[x]<inf?alldis[x]:-1)<<"\n";
    }
}

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