Submission #890433

#	Time	Username	Problem	Language	Result	Execution time	Memory
890433		alexander707070	Passport (JOI23_passport)	C++14	100 / 100	814 ms	166040 KiB

passport

#include<bits/stdc++.h>
#define MAXN 2000007
using namespace std;

const long long inf=1e15;

int n,q,x,minv;
int l[MAXN],r[MAXN];
vector< pair<int,long long> > g[MAXN];

long long dist[MAXN],cost[MAXN];
bool li[MAXN];

priority_queue< pair<long long,int> , vector< pair<long long,int> > , greater< pair<long long,int> > > pq;

void dijkstra(int x){
    for(int i=1;i<=5*n+10;i++){
        li[i]=false; dist[i]=inf;
    }

    pq.push({0,x});
    dist[x]=0;

    while(!pq.empty()){
        minv=pq.top().second;
        pq.pop();

        if(li[minv])continue;
        li[minv]=true;

        for(int i=0;i<g[minv].size();i++){
            if(li[g[minv][i].first] or dist[g[minv][i].first]<=dist[minv]+g[minv][i].second)continue;

            dist[g[minv][i].first]=dist[minv]+g[minv][i].second;
            pq.push({dist[g[minv][i].first],g[minv][i].first});
        }
    }
}

void build(int t,int l,int r){
    if(l==r){
        g[l+4*n].push_back({t,0});
    }else{
        int tt=(l+r)/2;

        g[2*t].push_back({t,0});
        build(2*t,l,tt);

        g[2*t+1].push_back({t,0});
        build(2*t+1,tt+1,r);
    }
}

void update(int t,int l,int r,int ll,int rr,int root){
    if(ll>rr)return;
    if(l==ll and r==rr){
        g[t].push_back({root,1});
    }else{
        int tt=(l+r)/2;
        update(2*t,l,tt,ll,min(tt,rr),root);
        update(2*t+1,tt+1,r,max(tt+1,ll),rr,root);
    }
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>l[i]>>r[i];
    }

    build(1,1,n);

    for(int i=1;i<=n;i++){
        update(1,1,n,l[i],r[i],i+4*n);
    }

    dijkstra(4*n+1); dist[4*n+1]=1;
    for(int i=1;i<=n;i++){
        cost[i]+=dist[4*n+i];
    }

    dijkstra(4*n+n); dist[4*n+n]=1;
    for(int i=1;i<=n;i++){
        cost[i]+=dist[4*n+i];
    }

    for(int i=1;i<=n;i++){
        g[5*n+1].push_back({i+4*n,cost[i]});
    }
    dijkstra(5*n+1);

    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>x;
        if(dist[4*n+x]==inf)cout<<"-1\n";
        else cout<<dist[4*n+x]-1<<"\n";
    }

    return 0;
}

Compilation message (stderr)

passport.cpp: In function 'void dijkstra(int)':
passport.cpp:31:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for(int i=0;i<g[minv].size();i++){
      |                     ~^~~~~~~~~~~~~~~

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