Submission #891660

#	Time	Username	Problem	Language	Result	Execution time	Memory
891660		PagodePaiva	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	946 ms	65972 KiB

Main

#include<bits/stdc++.h>
#define N 200010
#define LOGN 20
#define int long long

using namespace std;

struct DSU{
    int pai[N];   
    DSU(){
        for(int i = 0;i < N;i++){
            pai[i] = i;
        }
    }
    int find(int x){
        return (x == pai[x] ? x : find(pai[x]));
    }
    void join(int a, int b){
        b = find(b);
        pai[b] = a;
        return;                
    }
} dsu;

int n;
int p[N];
vector <pair <int,int>> ord;
vector <int> g[N];
int dp[N];
int h[N], pai[N][LOGN];

void dfs(int v, int p){
    pai[v][0] = p;
    for(auto x : g[v]){
        if(x == p) continue;
        h[x] = h[v]+1;
        dfs(x, v);
    }
    return;
}

int query(int x, int y){
    if(h[x] > h[y]) swap(x, y);
    int t = h[y] - h[x];
    int res = 0;
    for(int i = 0;i < LOGN;i++){
        if((t & (1 << i))){
            int pp = (1 << i);
            res += pp;
            y = pai[y][i];
        }
    }
    if(x == y) return res;
    for(int i = LOGN-1;i >= 0;i--){
        if(pai[x][i] != pai[y][i]){
            x = pai[x][i];
            y = pai[y][i];
            int pp = (1 << i);
            res += 2*pp;
        }
    }
    return res+2;
}

int32_t main(){
    cin >> n;
    for(int i = 1;i <= n;i++){
        int x;
        cin >> x;
        p[i] = x;
        ord.push_back({x, i});
    }
    sort(ord.begin(), ord.end());
    for(int i = 1;i < n;i++){
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1, 1);
    for(int i = 1;i < LOGN;i++){
        for(int v = 1;v <= n;v++){
            pai[v][i] = pai[pai[v][i-1]][i-1];
        }
    }
    for(auto aa : ord){
        int v = aa.second;
        for(auto x : g[v]){
            if(p[x] > p[v]) continue;
            int t = dsu.find(x);
            dp[p[v]] = max(dp[p[v]], dp[p[t]] + query(v, t));
            dsu.join(v, t);
        }   
    }
    cout << dp[n] << endl;
}

• 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