Submission #745801

#	Time	Username	Problem	Language	Result	Execution time	Memory
745801		snpmrnhlol	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	345 ms	63352 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2e5;
ll v[N],pos[N];
vector <ll> e[N];
struct DSU{
    ll parent,score,maxx,power;
}v2[N];
ll leader(ll node){
    if(v2[node].parent == node){
        return node;
    }else{
        v2[node].parent = leader(v2[node].parent);
        return v2[node].parent;
    }
}
void connect(ll a,ll b){
    a = leader(a);
    b = leader(b);
    if(v2[a].power > v2[b].power)swap(a,b);
    v2[a].parent = b;
    v2[b].power+=v2[a].power;
    v2[b].score = max(v2[b].score,v2[a].score);
    if(v[v2[b].maxx] < v[v2[a].maxx]){
        v2[b].maxx = v2[a].maxx;
    }
}
ll p[N][20],dpth[N];
void dfs(ll node,ll parent = 0,ll d = 0){
    p[node][0] = parent;
    dpth[node] = d;
    for(auto i:e[node]){
        if(i == parent)continue;;
        dfs(i,node,d + 1);
    }
}
ll LCA(ll a,ll b){
    if(dpth[a] > dpth[b])swap(a,b);
    for(ll i = 19;i >= 0;i--){
        if(dpth[b] - (1<<i) >= dpth[a]){
            b = p[b][i];
        }
    }
    for(ll i = 19;i >= 0;i--){
        if(p[a][i] != p[b][i]){
            b = p[b][i];
            a = p[a][i];
        }
    }
    if(a != b)return p[a][0];
    return a;
}
ll fastp(ll node,ll nr){
    for(ll i = 19;i >= 0;i--){
        if(nr - (1<<i) >= 0){
            nr-=(1<<i);
            node = p[node][i];
        }
    }
    return node;
}
ll dist(ll a,ll b){
    return dpth[a] + dpth[b] - 2*dpth[LCA(a,b)];
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n,i,u,w,j;
    cin>>n;
    for(i=  0;i < n;i++){
        cin>>v[i];pos[--v[i]] = i;
    }
    for(i = 0;i < n - 1;i++){
        cin>>u>>w;u--;w--;
        e[u].push_back(w);
        e[w].push_back(u);
    }
    dfs(0);
    for(j = 1;j < 20;j++){
        for(i = 0;i < n;i++){
            p[i][j] = p[p[i][j - 1]][j - 1];
        }
    }
    for(i = 0;i < n;i++)v2[i] = {i,0,i,i};
    for(i = 0;i < n;i++){
        ll score = 1;
        for(auto j:e[pos[i]]){
            if(v[pos[i]] > v[j]){
                ///good and fucked already
                ll l = leader(j);
                score = max(v2[l].score + dist(v2[l].maxx,pos[i]),score);
            }
        }
        //cout<<pos[i]<<' '<<score<<'\n';
        v2[pos[i]].score = score;
        for(auto j:e[pos[i]]){
            if(v[pos[i]] > v[j]){
                connect(pos[i],j);
            }
        }
    }
    cout<<v2[leader(0)].score - 1;
    return 0;
}

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