Submission #1076803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076803		dwuy	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	128 ms	41720 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
const int MX = 200005;
int n;
int a[MX];
int e[MX];
int mx[MX];
int res[MX];
vector<int> G[MX];

void nhap(){
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<n; i++){
        int u, v;
        cin >> u >> v;
        G[a[u]].push_back(a[v]);
        G[a[v]].push_back(a[u]);
    }
}

namespace HLD{
    int h[MX];
    int p[MX];
    int numC[MX];
    int heavy[MX];
    int head[MX];

    void dfs(int u){
        numC[u] = 1;
        h[u] = h[p[u]] + 1;
        for(int v: G[u]) if(v != p[u]){
            p[v] = u;
            dfs(v);
            numC[u] += numC[v];
            if(numC[v] > numC[heavy[u]]) heavy[u] = v;
        }
    }

    void decompose(int u, int he){
        head[u] = he;
        if(heavy[u]) decompose(heavy[u], he);
        for(int v: G[u]) if(v != heavy[u] && v != p[u]){
            decompose(v, v);
        }
    }

    int dis(int u, int v){
        int res = 0;
        while(head[u] != head[v]){
            if(h[head[u]] < h[head[v]]) swap(u, v);
            res += h[u] - h[head[u]] + 1;
            u = p[head[u]];
        }
        res += abs(h[u] - h[v]);
        return res;
    }

    void build(){
        dfs(1);
        decompose(1, 1);
    }
}

int fp(int u){
    return e[u] < 0? u : e[u] = fp(e[u]);
}

void solve(){
    HLD::build();

    memset(e, -1, sizeof e);
    memset(res, 0, sizeof res);
    for(int i=1; i<=n; i++) mx[i] = i;

    for(int u=1; u<=n; u++){
        int best = 0;
        for(int x: G[u]) if(x < u){
            int v = fp(x);
            best = max(best, res[v] + HLD::dis(u, mx[v]));
            int t = fp(u);
            if(e[t] > e[v]) swap(t, v);
            e[v] += e[t];
            e[t] = v;
        }
        int t = fp(u);
        res[t] = best;
        mx[t] = u;
    }
    cout << res[fp(n)];
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    nhap();
    solve();

    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