제출 #873203

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
873203		PagodePaiva	Cat Exercise (JOI23_ho_t4)	C++17	7 / 100	2 ms	10844 KiB

Main

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

using namespace std;

int n;
int v[N];
vector <int> g[N];
vector <pair <int, int>> pp;
int res[N];

struct DSU{
    int pai[N];

    void init(){
        for(int i = 1;i <= n;i++) pai[i] = i;
    }

    int find(int x){
        return pai[x] = (x == pai[x] ? x : find(pai[x]));
    }

    void join(int a, int b){
        b = find(b);
        pai[b] = a;
        return;
    }
} dsu;

struct Sparse{
    int pai[N][LOGN];
    int height[N];


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

    void init(){
        height[1] = 0;
        dfs(1, 1);

        for(int t = 1;t < LOGN;t++){
            for(int i = 1;i <= n;i++){
                pai[t][i] = pai[pai[t][i-1]][i-1];
            }
        }
    }

    int query(int x, int y){
        if(height[x] > height[y]) swap(x, y);
        
        int t = height[y] - height[x];

        for(int i = 0;i < LOGN;i++){
            if((t & (1 << i)) != 0){
                y = pai[y][i];
            }
        }

        if(x == y) return x;

        for(int i = LOGN-1;i >= 0;i--){
            if(pai[x][i] != pai[y][i]){
                x = pai[x][i];
                y = pai[y][i];
            }
        }

        return pai[x][0];
    }

    int dist(int x, int y, int lca){
        return height[x] + height[y] - 2*height[lca];
    }
} sparse;

int dist(int x, int y){
    int lca = sparse.query(x, y);

    return sparse.dist(x, y, lca);
}
int32_t main(){
    cin >> n;

    for(int i = 1;i <= n;i++) cin >> v[i];

    for(int i = 1;i < n;i++){
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    for(int i = 1;i <= n;i++){
        pp.push_back({v[i], i});
    }

    dsu.init();
    sparse.init();

    sort(pp.begin(), pp.end());

    for(auto aa : pp){
        int ver = aa.second;
        // cout << ver << '\n';

        for(auto x : g[ver]){
            if(v[x] > v[ver]) continue;
            x = dsu.find(x);
            // cout << x << ' ';
            res[ver] = max(res[ver], res[x] + dist(x, ver));
            dsu.join(ver, x);
        }

        // cout << '\n';
        // cout << '\n';   
    }

    int resp = 0;

    for(int i = 1;i <= n;i++) {resp = max(resp, res[i]);}

    cout << resp << '\n';
}

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