Submission #915962

#	Time	Username	Problem	Language	Result	Execution time	Memory
915962		imarn	Passport (JOI23_passport)	C++14	46 / 100	824 ms	95880 KiB

passport

#include<bits/stdc++.h>
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define pb push_back
#define f first
#define s second
#define vi vector<ll>
#define vvi vector<vi>
#define vpii vector<pii>
#define ll long long
#define sz(x) (int)x.size()
using namespace std;
const int N=2e5+5;
vector<pii>g[6*N];
int n;
void build(int i,int l,int r){
    if(l==r)return void(g[l].pb({i+n,0}));
    int m=(l+r)>>1;build(2*i,l,m);build(2*i+1,m+1,r);
    g[2*i+n].pb({i+n,0});g[2*i+1+n].pb({i+n,0});
}
void upd(int i,int l,int r,int tl,int tr,int id){
    if(r<tl||l>tr)return;
    if(r<=tr&&l>=tl){
        g[i+n].pb({id,1});return;
    }int m=(l+r)>>1;
    upd(2*i,l,m,tl,tr,id);upd(2*i+1,m+1,r,tl,tr,id);
}
int d[3][6*N];
bool vis[6*N]{0};
void distar(int st,int i){
    for(int v=0;v<6*N;v++)d[i][v]=1e9;
    d[i][st]=0;priority_queue<pii,vector<pii>,greater<pii>>pq;
    pq.push({0,st});
    while(!pq.empty()){
        auto u=pq.top();pq.pop();
        if(vis[u.s])continue;
        vis[u.s]=1;
        for(auto v:g[u.s]){
            if(d[i][v.f]>u.f+v.s)d[i][v.f]=u.f+v.s,pq.push({d[i][v.f],v.f});
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;build(1,1,n);
    for(int i=1;i<=n;i++){
        int l,r;cin>>l>>r;upd(1,1,n,l,r,i);
    }distar(1,0);memset(vis,0,sizeof vis);distar(n,1);memset(vis,0,sizeof vis);
    for(int i=0;i<6*N;i++)d[2][i]=1e9;priority_queue<pii,vector<pii>,greater<pii>>pq;
    for(int i=1;i<=n;i++)d[2][i]=d[0][i]+d[1][i]-(i>1&&i<n),pq.push({d[2][i],i});
    while(!pq.empty()){
        auto u=pq.top();pq.pop();
        if(vis[u.s])continue;
        vis[u.s]=1;
        for(auto v:g[u.s]){
            if(d[2][v.f]>u.f+v.s)d[2][v.f]=u.f+v.s,pq.push({d[2][v.f],v.f});
        }
    }int q;cin>>q;
    while(q--){
        int x;cin>>x;cout<<(d[2][x]==1e9?-1:d[2][x])<<'\n';
    }
}

Compilation message (stderr)

passport.cpp: In function 'int main()':
passport.cpp:51:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   51 |     for(int i=0;i<6*N;i++)d[2][i]=1e9;priority_queue<pii,vector<pii>,greater<pii>>pq;
      |     ^~~
passport.cpp:51:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   51 |     for(int i=0;i<6*N;i++)d[2][i]=1e9;priority_queue<pii,vector<pii>,greater<pii>>pq;
      |                                       ^~~~~~~~~~~~~~

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