Submission #932955

#	Time	Username	Problem	Language	Result	Execution time	Memory
932955		owoovo	Passport (JOI23_passport)	C++14	100 / 100	798 ms	235252 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],dis1[800010],dis2[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],dis1,hparg);
    distra(id[n],dis2,hparg);

    for(int i=1;i<=n;i++)hparg[0].push_back({id[i],max(0ll,dis1[id[i]]-1)+max(0ll,dis2[id[i]]-1)+1});

    distra(0,dis1,hparg);
    cin>>q;
    for(int i=1;i<=q;i++){
        int v;
        cin>>v;
        if(dis1[id[v]]<maxn)cout<<dis1[id[v]]<<"\n";
        else cout<<"-1\n";
    }
    return 0;
}

Compilation message (stderr)

passport.cpp: In function 'void distra(long long int, long long int*, std::vector<std::pair<long long int, long long int> >*)':
passport.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |         auto [d,v]=pq.top();
      |              ^
passport.cpp:44:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |         for(auto &[ne,w]:(*(graph+v))){
      |                   ^
passport.cpp: In function 'int main()':
passport.cpp:64:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |         for(auto &[v,w]:graph[i]){
      |                   ^

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