Submission #917082

#	Time	Username	Problem	Language	Result	Execution time	Memory
917082		manizare	Passport (JOI23_passport)	C++14	100 / 100	1474 ms	215720 KiB

passport

#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define int long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
using namespace std ;   
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 3e6 + 10 , inf= 1e17 ;
vector <pii> G[maxn] ;int n , m ,id[maxn] , cnt , ans[maxn] , d1[maxn] , d2[maxn] , mark[maxn]  ; 

void add(int v ,int u , int w){
    G[u].pb({v,w}); 
}

void upd(int x ,int w , int le , int ri , int p = 1, int l = 1 , int r= n){
    int pl = p<<1 , pr = p<<1 | 1 , mid = (l+r)/2 ;
    if(le > r || l > ri){
        return ;
    }
    if(le <= l&& r <= ri){
        add(x , id[p] , w) ;
        return ;
    }
    upd(x,w,le,ri,pl,l,mid);
    upd(x,w,le,ri,pr,mid+1,r);
}
void bui(int p = 1 , int l = 1 , int r=n){
    int pl = p<<1 , pr = p<<1 | 1 , mid = (l+r)/2 ;
    id[p] = cnt ;cnt++;
    if(l ==r){
        add(id[p] , l , 0);
        return ;
    }
    bui(pl,l,mid);
    bui(pr,mid+1,r); 
    add(id[p] , id[pl] , 0) ;
    add(id[p] , id[pr] , 0) ;

}


signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n  ;
    cnt = n+1; 
    bui() ;
    rep(i , 1 ,n){
        int c , w , v , u ;
        cin >> v >> u ;
        c= i ;
        w = 1; 
        if(v > u)swap(v,u) ;
        add(c , cnt , w);
        upd(cnt , 0 , v , u) ;
        cnt++;
    }
    rep(i , 1, cnt){
        d1[i] = d2[i] = inf ;
    }
    priority_queue <pii> pq ;
    d1[1] = 0 ;pq.push({0,1});
    while(sz(pq)){
        int v = pq.top().S ; pq.pop();
        if(mark[v] == 1)continue ;
        mark[v] = 1;
        for(pii u : G[v]){
            if(d1[u.F] > d1[v] + u.S){
                d1[u.F] =d1[v] + u.S;
                pq.push({-d1[u.F] , u.F}) ;
            }
        }
    }
    rep(i , 1, cnt)mark[i] = 0 ;
    d2[n] = 0;pq.push({0,n});
    while(sz(pq)){
        int v = pq.top().S ; pq.pop();
        if(mark[v] == 1)continue ;
        mark[v] = 1;
        for(pii u : G[v]){
            if(d2[u.F] > d2[v] + u.S){
                d2[u.F] =d2[v] + u.S;
                pq.push({-d2[u.F] , u.F}) ;
            }
        }
    }
    rep(i , 1, cnt){
        ans[i] = d1[i] + d2[i] ;
        pq.push({-ans[i] , i}) ;
    }
    rep(i , 1 ,cnt)mark[i] =0 ;
    while(sz(pq)){
        int v = pq.top().S ; pq.pop();
        if(mark[v] == 1)continue ;
        mark[v] = 1;
        for(pii u : G[v]){
            if(ans[u.F] > ans[v] + u.S){
                ans[u.F] =ans[v] + u.S;
                pq.push({-ans[u.F] , u.F}) ;
            }
        }
    }
    int q;
    cin >> q; 
    rep(i , 1, q){
        int x;
        cin >> x ;
        if(ans[x] >= inf){
            cout << -1 << "\n";
        }else{
            cout << ans[x] << "\n"; 
        }
    }
}

/*

}
*/

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