Submission #835037

#	Time	Username	Problem	Language	Result	Execution time	Memory
835037		isaachew	Cat Exercise (JOI23_ho_t4)	C++17	54 / 100	244 ms	40836 KiB

Main

#include <bits/stdc++.h>
/*
 When you are at node k, you cannot go to any node > k as that is unreachable
 */
struct dsu{
    std::vector<int> parents;
    std::vector<int> maxes;
    dsu(int n){
        parents.resize(n,-1);
        for(int i=0;i<n;i++){
            maxes.push_back(i);
        }
    }
    void combine(int a,int b){
        a=find(a),b=find(b);
        parents[a]=b;
        maxes[b]=std::max(maxes[a],maxes[b]);
    }
    int find(int x){
        if(parents[x]==-1)return x;
        else{
            return (parents[x]=find(parents[x]));
        }
    }
};
std::vector<std::vector<int>> edges;
std::vector<int> depths;
std::vector<int> parents;
std::vector<std::vector<int>> binlifts;
void dfs(int cur,int parent){
    parents[cur]=parent;
    for(int i:edges[cur]){
        if(i==parent)continue;
        depths[i]=depths[cur]+1;
        dfs(i,cur);
    }
}
int lca(int a,int b){
    if(depths[a]<depths[b])std::swap(a,b);
    for(int i=20;i--;){
        if(depths[a]-(1<<i)>=depths[b]){
            a=binlifts[i][a];
        }
    }
    if(a==b)return a;//a is an ancestor/descendant of b
    for(int i=20;i--;){
        int na=binlifts[i][a],nb=binlifts[i][b];
        if(na!=nb){
            a=na,b=nb;
        }
    }
    return parents[a];
}
int getdist(int a,int b){
    int clca=lca(a,b);
    return depths[a]+depths[b]-2*depths[clca];
}
int main(){
    int n;
    std::cin>>n;
    std::vector<int> theights;
    std::vector<int> scores(n);
    depths.resize(n);
    edges.resize(n);
    binlifts.resize(20);
    parents.resize(n);
    dsu conncs(n);
    for(int i=0;i<n;i++){
        int x;
        std::cin>>x;
        x--;
        theights.push_back(x);
    }
    for(int i=1;i<n;i++){
        int a,b;
        std::cin>>a>>b;
        a=theights[a-1],b=theights[b-1];
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    dfs(0,0);
    binlifts[0]=parents;
    for(int i=0;i<19;i++){
        for(int j=0;j<n;j++){
            binlifts[i+1].push_back(binlifts[i][binlifts[i][j]]);
        }
    }
    for(int i=0;i<n;i++){
        int cscore=0;
        for(int j:edges[i]){
            if(j>i)continue;
            int jpcc=conncs.maxes[conncs.find(j)];
            cscore=std::max(cscore,scores[jpcc]+getdist(i,jpcc));
            conncs.combine(i,jpcc);
        }
        scores[i]=cscore;
    }
    std::cout<<scores.back()<<'\n';
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 23 / 23
• Subtask 7: 0 / 26