Submission #1012513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012513		Pacybwoah	Passport (JOI23_passport)	C++17	100 / 100	773 ms	150908 KiB

passport

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#define int ll
using namespace std;
typedef long long ll;
vector<vector<pair<int,ll> > > graph;
vector<int> pos;
void build(int l,int r,int ind){
    if(l==r){
        pos[l]=ind;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ind*2);
    build(mid+1,r,ind*2+1);
    graph[ind*2].push_back(make_pair(ind,0));
    graph[ind*2+1].push_back(make_pair(ind,0));
}
void modify(int l,int r,int start,int end,int s,ll num,int ind){
    if(r<start||end<l) return;
    if(start<=l&&r<=end){
        graph[ind].push_back(make_pair(s,num));
        return;
    }
    int mid=(l+r)>>1;
    modify(l,mid,start,end,s,num,ind*2);
    modify(mid+1,r,start,end,s,num,ind*2+1);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n;
    m = n;
    graph.resize(4*n+4+m);
    pos.resize(n+1);
    build(1,n,1);
    int a,b;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        modify(1,n,a,b,4*n+4+i,0,1);
        graph[4*n+4+i].push_back(make_pair(pos[i + 1],1));
    }
    priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > pq;
    vector<ll> dist1(4*n+4+m,1e18),distn(4*n+4+m,1e18);
    auto dijk=[&](vector<ll> &dist){
        while(!pq.empty()){
            auto [d,node]=pq.top();
            pq.pop();
            //cout<<d<<'\n';
            if(d!=dist[node]) continue;
            for(auto &[x,l]:graph[node]){
                if(dist[x]>d+l){
                    dist[x]=d+l;
                    pq.push(make_pair(dist[x],x));
                }
            }
        }
    };
    pq.push(make_pair(0,pos[1]));
    dist1[pos[1]]=0;
    dijk(dist1);
    //for(int i=4*n+4;i<4*n+4+m;i++) cout<<dist1[i]<<' ';
    //cout<<"\n";
    //for(int i=1;i<=n;i++) cout<<dist1[pos[i]]<<' ';
    pq.push(make_pair(0,pos[n]));
    distn[pos[n]]=0;
    dijk(distn);
    vector<ll> dist(4*n+4+m,1e18);
    for(int i=1;i<=4*n+3+m;i++) dist[i]=min(dist[i],dist1[i]+distn[i]);
    for(int i=1;i<=4*n+3+m;i++) if(dist[i]<1e18) pq.push(make_pair(dist[i],i));
    dijk(dist);
    int q;
    cin >> q;
    while(q--){
        int i;
        cin >> i;
        if(dist[pos[i]]>=1e18) cout<<"-1\n";
        else cout<<dist[pos[i]]<<"\n";
    }
}

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