Submission #906066

#	Time	Username	Problem	Language	Result	Execution time	Memory
906066		ThylOne	Passport (JOI23_passport)	C++14	100 / 100	1268 ms	84160 KiB

passport

//####################
//PassportJOI
//####################
#include<bits/stdc++.h>

using namespace std;
using vi = vector<int>;
struct segtree{
    struct inter{
        int deb,fin;
        bool inclus_dans(inter I){
            return I.deb<=deb && fin<=I.fin;
        }
        bool exclus_de(inter I){
            return fin<I.deb || I.fin<deb;
        }
        inter gauche(){
            int mid = (deb+fin)/2;
            if(mid==fin)mid=deb;
            return {deb,mid};
        }
        inter droite(){
            int mid = (deb+fin)/2;
            if(mid==fin)mid=deb;
            return {mid+1,fin};
        }
    };
    vector<vi> nodes;
    int leaf;
    int nb_nums;
    segtree(int n){
        nb_nums=n;
        leaf = (1<<((int)ceil(log2(n))));
        nodes.resize(leaf*2);
    }
    void addVal(int node,inter act,inter request,int val){
        if(act.inclus_dans(request)){
            nodes[node].push_back(val);
        }else if(act.exclus_de(request)){
            return ;
        }else if(node<leaf){
            addVal(node*2,act.gauche(),request,val);
            addVal(node*2+1,act.droite(),request,val);
        }
    }
    void getNext(int node,inter act,int u,vector<int> &acc){
        if(!(act.deb<=u && u<=act.fin)){
            return;
        }
        for(int &v:nodes[node]){
            acc.push_back(v);
        }
        nodes[node].clear();
        nodes[node].shrink_to_fit();
        if(node<leaf){
            getNext(node*2,act.gauche(),u,acc);
            getNext(node*2+1,act.droite(),u,acc);
        }
    }
};
vector<pair<int,int>> passports;
vector<int> distN;
vector<int> dist1;
int n,q;
void bfs(int source,vector<int> &distances_bfs){
    fill(distances_bfs.begin(),distances_bfs.end(),-1);
    vi distances[n+1];
    distances[0].push_back(source);
    bool mem[n];
    fill(mem,mem+n,false);
    segtree st(n);
    for(int i = 0;i<n;i++){
        st.addVal(1,{0,st.leaf-1},{passports[i].first,passports[i].second},i);
    }
    //BFS
    for(int i = 0;i<=n;i++){
        for(int act:distances[i]){
            if(mem[act])continue;
            distances_bfs[act]=i;
            mem[act]=true;
            vi fils;
            st.getNext(1,{0,st.leaf-1},act,fils);
            for(int &f:fils){
                if(!mem[f]){
                    distances[i+1].push_back(f);
                }
            }
        }
    }
}
void bfs2(vector<int> &distances_bfs){
    fill(distances_bfs.begin(),distances_bfs.end(),-1);
    vi distances[5*n];
    bool mem[n];
    fill(mem,mem+n,false);
    segtree st(n);
    for(int i = 0;i<n;i++){
        st.addVal(1,{0,st.leaf-1},{passports[i].first,passports[i].second},i);
    }
    for(int i = 0;i<n;i++){
        if(dist1[i]==-1 || distN[i]==-1)continue;
        int d = dist1[i]+distN[i]-1;
        if(i==0 || i==n-1)d++;
        distances[d].push_back(i);
    }
    //BFS
    for(int i = 0;i<=5*n-1;i++){
        for(int act:distances[i]){
            if(mem[act])continue;
            distances_bfs[act]=i;
            mem[act]=true;
            vi fils;
            st.getNext(1,{0,st.leaf-1},act,fils);
            for(int &f:fils){
                if(!mem[f]){
                    distances[i+1].push_back(f);
                }
            }
        }
    }
}
signed main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int a,b;cin>>a>>b;
        a--;
        b--;
        passports.push_back({a,b});
    }
    distN.resize(n);
    dist1.resize(n);
   
    bfs(n-1,distN);
    bfs(0,dist1);
    vi ans(n);
    bfs2(ans);
    int q;cin>>q;
    for(int i = 0;i<q;i++){
        int query;cin>>query;
        query--;
        cout<<ans[query]<<'\n';
    }
    return 0;
};

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