Submission #831365

#	Time	Username	Problem	Language	Result	Execution time	Memory
831365		alvingogo	Passport (JOI23_passport)	C++14	100 / 100	684 ms	100296 KiB

passport

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

inline void chmin(int& a,int b){
    a=min(a,b);
}
typedef pair<int,int> pii;
struct TC{
    int c,p,a,b;
};
struct ST{
    struct no{
        vector<int> s;
        int vis=0;
    };
    vector<no> st;
    void init(int x){
        st.resize(4*x);
    }
    void update(int v,int L,int R,int l,int r,int a){
        if(L==l && r==R){
            st[v].s.push_back(a);
            return;
        }
        int m=(L+R)/2;
        if(r<=m){
            update(2*v+1,L,m,l,r,a);
        }
        else if(l>m){
            update(2*v+2,m+1,R,l,r,a);
        }
        else{
            update(2*v+1,L,m,l,m,a);
            update(2*v+2,m+1,R,m+1,r,a);
        }
    }
    void find(int v,int L,int R,int t,int g,vector<int>& a){
        if(st[v].vis!=g){
            st[v].vis=g;
            a.insert(a.end(),st[v].s.begin(),st[v].s.end());
        }
        if(L==R){
            return;
        }
        int m=(L+R)/2;
        if(t<=m){
            find(2*v+1,L,m,t,g,a);
        }
        else{
            find(2*v+2,m+1,R,t,g,a);
        }
    }
}st;
const int inf=1e18;
signed main(){
    AquA;
    int n,k;
    cin >> n;
    k=n;
    vector<TC> v(k);
    for(int i=0;i<k;i++){
        v[i].c=i;
        v[i].p=1;
        cin >> v[i].a >> v[i].b;
        v[i].a--;
        v[i].b--;
    }
    st.init(n);
    for(int i=0;i<k;i++){
        st.update(0,0,n-1,v[i].a,v[i].b,i+n);
    }
    auto dijk=[&](vector<int>& dis,int g){
        p_q<pii,vector<pii>,greater<pii> > pq;
        for(int i=0;i<n+k;i++){
            pq.push({dis[i],i});
        }
        while(pq.size()){
            auto h=pq.top();
            pq.pop();
            if(dis[h.sc]!=h.fs){
                continue;
            }
            if(h.sc>=n){
                int r=h.sc-n;
                if(dis[v[r].c]>h.fs+v[r].p){
                    dis[v[r].c]=h.fs+v[r].p;
                    pq.push({dis[v[r].c],v[r].c});
                }
            }
            else{
                vector<int> e;
                st.find(0,0,n-1,h.sc,g,e);
                for(auto y:e){
                    if(dis[y]>h.fs){
                        dis[y]=h.fs;
                        pq.push({dis[y],y});
                    }
                }
            }
        }
    };
    vector<int> a(n+k,inf),b(n+k,inf),ans(n+k);
    a[0]=0;
    dijk(a,1);
    b[n-1]=0;
    dijk(b,2);
    for(int i=0;i<n+k;i++){
        ans[i]=a[i]+b[i];
    }
    for(int i=n;i<n+k;i++){
        chmin(ans[v[i-n].c],ans[i]+v[i-n].p);
    }
    dijk(ans,3);
    int q;
    cin >> q;
    while(q--){
        int a;
        cin >> a;
        a--;
        if(ans[a]>=inf){
            cout << -1 << "\n";
        }
        else{
            cout << ans[a] << "\n";
        }
    }
    return 0;
}

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