Submission #906054

#	Time	Username	Problem	Language	Result	Execution time	Memory
906054		ThylOne	Passport (JOI23_passport)	C++14	6 / 100	395 ms	54136 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;
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);
                }
            }
        }
    }
}
signed main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int a,b;cin>>a>>b;
        a--;
        b--;
        passports.push_back({a,b});
    }

    vector<int> distN(n);
    bfs(n-1,distN);
    cout<<distN[0]<<endl;
    return 0;
};

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