Submission #1095388

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095388		hahahoang132	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	189 ms	64592 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 = 2e5 + 5;
const ll inf = LLONG_MAX/4;
ll p[N],h[N],ans[N],tmp[N];
ll par[21][N];
vector<ll> a[N];
ll fp(ll x)
{
    if(p[x] == -1) return x;
    else
    {
        p[x] = fp(p[x]);
        return p[x];
    }
}
ll lca(ll x, ll y)
{
    if(h[x] > h[y]) swap(x,y);
    ll dis = h[y] - h[x];
    ll i,j;
    for(i = 20;i >= 0;i--)
    {
        if(dis >= (1 << i))
        {
            y = par[i][y];
            dis -= (1 << i);
        }
    }
    if(x == y) return x;
    for(i = 20;i >= 0;i--)
    {
        if(par[i][x] != par[i][y])
        {
            x = par[i][x];
            y = par[i][y];
        }
    }
    return par[0][x];
}
void hop(ll x, ll y)
{
    ll px = x;
    ll py = fp(y);
    ll z = lca(px,py);
    ans[px] = max(ans[px],ans[py] + h[px] + h[py] - 2 * h[z]);
    p[py] = px;
}
void build(ll x, ll px)
{
    for(auto y : a[x])
    {
        if(y != px)
        {
            par[0][y] = x;
            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 <= 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;
        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 'long long int lca(long long int, long long int)':
Main.cpp:24:10: warning: unused variable 'j' [-Wunused-variable]
   24 |     ll i,j;
      |          ^

• 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