Submission #828064

#	Time	Username	Problem	Language	Result	Execution time	Memory
828064		LeVanThuc	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	340 ms	81824 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define p(x,y) pair<ll,ll>(x,y)
#define BIT(i,x) ((x>>i)&1)
#define MASK(x) (1<<x)
#define ld long double
#define __builtin_popcount __builtin_popcountll
#define pll pair<ll,ll>
template<class T1,class T2>
bool maximize(T1 &x,const T2 &y)
{
    if(x<y)
    {
        x=y;
        return 1;
    }
    return 0;
}
template<class T1,class T2>
bool minimize(T1 &x,const T2 &y)
{
    if(x>y)
    {
        x=y;
        return 1;
    }
    return 0;
}
void online()
{
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
}
const ll N=2e5+10;
ll par[N][30],lv[N],dis[N],a[N],r[N],n;
vector<ll> gr[N];
void dfs(ll u)
{
    for(auto v:gr[u])
    {
        if(v==par[u][0]) continue;
        par[v][0]=u;
        lv[v]=lv[u]+1;
        dis[v]=dis[u]+1;
        dfs(v);
    }
}
ll dist(ll u,ll v)
{
    ll res=dis[u]+dis[v];
    if(lv[u]<lv[v]) swap(u,v);
    for(int i=20;i>=0;i--) if(lv[par[u][i]]>=lv[v]) u=par[u][i];
    if(u==v) return res-2*dis[u];
    for(int i=20;i>=0;i--)
    {
        if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];
    }
    u=par[u][0];
    return res-2*dis[u];
}
struct DSU
{
    ll n;
    vector<ll> best,f,lab;
    DSU(ll _n=0)
    {
        n=_n;
        f.resize(n+2);
        lab.resize(n+2,-1);
        best.resize(n+2);
    }
    ll root(ll x)
    {
        return lab[x]<0?x:lab[x]=root(lab[x]);
    }
    ll join(ll x,ll y)
    {
        if(best[x]==0||best[y]==0) return 0;
        if((x=root(x))==(y=root(y))) return 0;
        if(lab[x]>lab[y]) swap(x,y);
        lab[x]+=lab[y];
        lab[y]=x;
        return 1;
    }
};
int main()
{
    online();
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        r[a[i]]=i;
    }
    for(int i=1;i<n;i++)
    {
        ll u,v;
        cin>>u>>v;
        gr[u].push_back(v);
        gr[v].push_back(u);
    }
    dfs(1);
    for(int i=1;i<=20;i++)
    {
        for(int j=1;j<=n;j++) par[j][i]=par[par[j][i-1]][i-1];
    }
    DSU S(n);
    for(int i=1;i<=n;i++)
    {
        ll u=r[i];
        S.best[u]=i;
        ll c=0;
        for(auto V:gr[u]) 
        {
            ll v=S.root(V);
            if(S.best[v]==0) continue;
            maximize(c,S.f[v]+dist(u,r[S.best[v]]));
        }
        for(auto v:gr[u]) S.join(u,v);
        S.best[S.root(u)]=i;
        S.f[S.root(u)]=c;
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        maximize(ans,S.f[i]);
    }
    cout<<ans;
}

• 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