oj.uz

Submission #906054

# Submission time Handle Problem Language Result Execution time Memory
906054 2024-01-13T12:27:25 Z ThylOne Passport (JOI23_passport) C++14
6 / 100
 395 ms 54136 KB 
//####################
//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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 395 ms 54136 KB Output is correct
5 Correct 251 ms 32720 KB Output is correct
6 Correct 179 ms 31904 KB Output is correct
7 Correct 138 ms 35288 KB Output is correct
8 Correct 110 ms 35616 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 395 ms 54136 KB Output is correct
5 Correct 251 ms 32720 KB Output is correct
6 Correct 179 ms 31904 KB Output is correct
7 Correct 138 ms 35288 KB Output is correct
8 Correct 110 ms 35616 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -