Submission #1185634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185634		Hanksburger	Cat Exercise (JOI23_ho_t4)	C++20	54 / 100	104 ms	36492 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int par[20][200005], depth[200005], a[200005], PAR[200005], dp[200005];
vector<int> adj[200005];
void dfs(int u, int p)
{
    par[0][u]=p;
    for (int i=1; i<20; i++)
        par[i][u]=par[i-1][par[i-1][u]];
    for (int v:adj[u])
    {
        if (v==p)
            continue;
        depth[v]=depth[u]+1;
        dfs(v, u);
    }
}
int lca(int u, int v)
{
    if (depth[u]<depth[v])
        swap(u, v);
    int d=depth[u]-depth[v];
    for (int i=0; i<20; i++)
        if (d&(1<<i))
            u=par[i][u];
    if (u==v)
        return u;
    for (int i=19; i>=0; i--)
        if (par[i][u]!=par[i][v])
            u=par[i][u], v=par[i][v];
    return par[0][u];
}
int dist(int u, int v)
{
    return depth[u]+depth[v]-depth[lca(u, v)]*2;
}
int findPAR(int u)
{
    return PAR[u]==u?u:(PAR[u]=findPAR(PAR[u]));
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    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;
        adj[a[u]].push_back(a[v]);
        adj[a[v]].push_back(a[u]);
    }
    dfs(1, 1);
    for (int i=1; i<=n; i++)
        PAR[i]=i;
    for (int u=1; u<=n; u++)
    {
        for (int v:adj[u])
        {
            if (v>u)
                continue;
            v=findPAR(v);
            dp[u]=max(dp[u], dp[v]+dist(u, v));
            PAR[v]=u;
        }
    }
    cout << dp[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