Submission #834133

#	Time	Username	Problem	Language	Result	Execution time	Memory
834133		fdnfksd	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	309 ms	62080 KiB

Main

#include<bits/stdc++.h>
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll lab[maxN],h[maxN],P[maxN][18];

ll findset(ll x)
{
    return lab[x]<0?x:lab[x]=findset(lab[x]);
}
void unite(ll u,ll v)
{
    u=findset(u);
    v=findset(v);
    if(lab[u]>lab[v]) swap(u,v);
    lab[u]+=lab[v];
    lab[v]=u;
}
vector<ll>g[maxN];
void dfs(ll u,ll p)
{
    P[u][0]=p;
    for(int i=1;i<=17;i++) P[u][i]=P[P[u][i-1]][i-1];
    for(int v:g[u])
    {
        if(v!=p)
        {
            h[v]=h[u]+1;
            dfs(v,u);
        }
    }
}
ll lca(ll u,ll v)
{
    if(h[u]<h[v]) swap(u,v);
    for(int i=17;i>=0;i--) if(h[u]-(1<<i)>=h[v]) u=P[u][i];
    if(u==v) return u;
    for(int i=17;i>=0;i--) if(P[u][i]!=P[v][i]) u=P[u][i],v=P[v][i];
    return P[u][0];
}
ll dis(ll u,ll v)
{
    return h[u]+h[v]-2*h[lca(u,v)];
}
ll n,p[maxN],id[maxN],dp[maxN],mx[maxN];
void solve()
{
    cin >> n ;
    for(int i=1;i<=n;i++)
    {
        cin >> p[i];
        id[p[i]]=i;lab[i]=-1;
    }
    for(int i=1;i<n;i++)
    {
        ll u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1,1);
    for(int i=1;i<=n;i++)
    {
        ll u=id[i];
        for(int v:g[u])
        {
            if(p[v]<p[u])
            {
                dp[u]=max(dp[u],dp[findset(v)]+dis(u,mx[findset(v)]));
                unite(u,v);
            }
        }
        dp[findset(u)]=dp[u];
        mx[findset(u)]=u;
    }
    cout << dp[id[n]];
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

• 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