Submission #932949

#	Time	Username	Problem	Language	Result	Execution time	Memory
932949		owoovo	Passport (JOI23_passport)	C++17	6 / 100	804 ms	235632 KiB

passport

#include<bits/stdc++.h>
#define F first 
#define S second 
#define int long long
using namespace std;
const int maxn=1e17;
vector<pair<int,int>> graph[800010],hparg[800010];
int n,q,cnt,id[200010],on[800010],dis[800010];
void build(int l,int r,int now){
    if(l==r){
        id[l]=now;
        return;
    }
    int m=(l+r)>>1;
    graph[now].push_back({now*2,0});
    graph[now].push_back({now*2+1,0});
    build(l,m,now*2);
    build(m+1,r,now*2+1);
    return;
}
void pls(int l,int r,int tl,int tr,int nid,int uid){
    if(tl==l&&r==tr){
        graph[uid].push_back({nid,1});
        return;
    }
    int m=(l+r)>>1;
    if(tr<=m)pls(l,m,tl,tr,nid*2,uid);
    else if(m+1<=tl)pls(m+1,r,tl,tr,nid*2+1,uid);
    else{
        pls(l,m,tl,m,nid*2,uid);
        pls(m+1,r,m+1,tr,nid*2+1,uid);
    }
    return;
}
void distra(int s,int* dis,vector<pair<int,int>>* graph){
    priority_queue< pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>> > pq;
    for(int i=0;i<=800000;i++)*(dis+i)=maxn;
    (*(dis+s))=0;
    pq.push({0ll,s});
    while(!pq.empty()){
        auto [d,v]=pq.top();
        pq.pop();
        if(d>(*(dis+v)))continue;
        for(auto &[ne,w]:(*(graph+v))){
            if((*(dis+ne))>w+d){
                (*(dis+ne))=w+d;
                pq.push({w+d,ne});
            }    
        }
    }
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    build(1,n,1);
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        pls(1,n,l,r,1,id[i]);
    }
    for(int i=1;i<=800000;i++){
        for(auto &[v,w]:graph[i]){
            hparg[v].push_back({i,w});
        }
    }
    distra(id[1],dis,hparg);
    for(int i=1;i<=800000;i++){
        on[i]+=dis[i];
    }
    distra(id[n],dis,hparg);
    for(int i=1;i<=800000;i++){
        on[i]+=dis[i];
    }
    for(int i=1;i<=800000;i++){
        hparg[0].push_back({i,on[i]});
    }
    distra(0,dis,hparg);
    cin>>q;
    for(int i=1;i<=q;i++){
        int v;
        cin>>v;
        if(dis[id[v]]<maxn)cout<<dis[id[v]]<<"\n";
        else cout<<"-1\n";
    }
    return 0;
}

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