Submission #1241632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241632		hahahoang132	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	155 ms	81736 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 1e6 + 5;
const ll inf = LLONG_MAX/5;

ll par[25][N],tmp[N],h[N],p[N],d[N];
vector<ll> a[N];
void build(ll x, ll px)
{
    for(auto y : a[x])
    {
        if(y == px) continue;
        par[0][y] = x;
        h[y] = h[x] + 1;
        build(y,x);
    }
}
ll fp(ll x)
{
    if(p[x] == 0) return x;
    else
    {
        p[x] = fp(p[x]);
        return p[x];
    }
}
ll cntpath(ll x, ll y)
{
    ll i,j;
    if(h[x] < h[y]) swap(x,y);
    ll ans = 0;
    for(i = 20;i >= 0;i--)
    {
        if(h[par[i][x]] >= h[y])
        {
            ans += (1LL << i);
            x = par[i][x];
        }
    }
    if(x == y) return ans;
    for(i = 20;i >= 0;i--)
    {
        if(par[i][x] != par[i][y])
        {
            ans += 2 * (1LL << i);
            x = par[i][x];
            y = par[i][y];
        }
    }
    ans += 2;
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    cin >> n;
    ll i,j;
    for(i = 1;i <= n;i++)
    {
        ll tm;
        cin >> tm;
        tmp[i] = tm;
    }
    for(i = 1;i < n;i++)
    {
        ll u,v;
        cin >> u >> v;
        u = tmp[u];
        v = tmp[v];
        a[u].push_back(v);
        a[v].push_back(u);
    }
    h[1] = 1;
    build(1,0);
    for(i = 1;i <= 20;i++)
    {
        for(j = 1;j <= n;j++) par[i][j] = par[i - 1][par[i - 1][j]];
    }
    for(i = 1;i <= n;i++) p[i] = -1;
    for(i = 1;i <= n;i++)
    {
        ll x = i;
        p[x] = 0;
        for(auto y : a[x])
        {
            if(p[y] >= 0)
            {
                d[x] = max(d[x],d[fp(y)] + cntpath(x,fp(y)));
                p[fp(y)] = x;
            }
        }
    }
    cout << d[n];
}

• 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