Submission #1095383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095383		hahahoang132	Cat Exercise (JOI23_ho_t4)	C++17	41 / 100	89 ms	45728 KiB

Main

#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define bit(x,y) ((x >> y) & 1LL)
const ll mod = 1e9 + 7;
const ll N = 1e6 + 5;
const ll inf = LLONG_MAX/4;
ll p[N],h[N],ans[N],tmp[N];
vector<ll> a[N];
ll fp(ll x)
{
    if(p[x] == -1) return x;
    else
    {
        p[x] = fp(p[x]);
        return p[x];
    }
}
void hop(ll x, ll y)
{
    ll px = x;
    ll py = fp(y);
    ans[px] = max(ans[px],ans[py] + abs(h[px] - h[py]));
    p[py] = px;
}
void build(ll x, ll px)
{
    for(auto y : a[x])
    {
        if(y != px)
        {
            h[y] = h[x] + 1;
            build(y,x);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    cin >> n;
    ll i,j;
    for(i = 1;i <= n;i++)
    {
        cin >> tmp[i];
    }
    for(i = 1;i < n;i++)
    {
        ll u,v;
        cin >>  u>> v;
        a[tmp[u]].push_back(tmp[v]);
        a[tmp[v]].push_back(tmp[u]);
    }
    build(n,0);
    for(i = 1;i <= n;i++)
    {
        p[i] = -1;
        ans[i] = 0;
    }
    for(i = 1;i <= n;i++)
    {
        for(auto x : a[i])
        {
            if(x < i) hop(i,x);
        }
    }
    cout << ans[n];
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:43:10: warning: unused variable 'j' [-Wunused-variable]
   43 |     ll i,j;
      |          ^

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