Submission #1188346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188346		user736482	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	381 ms	136512 KiB

Main

#pragma GCC optimize("Ofast","unroll-loops","inline")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL
#define POT (1<<20)
ll a,b,r,c,t,n,m,l,q,k,ak,ans,s;
ll wys[200007],pre[200007],mxpre[200007],kto[200007],gdzie[200007],dpt[200007],pier[200007];
ll mn[400007][20];
pair<ll,ll> sgtree[POT];
vector<ll>g[200007],d[200007],pth;
void upd(ll v){
    if(!v)return;
    sgtree[v]=max(sgtree[v*2],sgtree[v*2+1]);
    upd(v/2);
}
pair<ll,ll>mx(ll pocz,ll kon,ll l,ll r,ll v){
    if(l>kon || r<pocz)return {0,0};
    if(l>=pocz && r<=kon)return sgtree[v];
    return max(mx(pocz,kon,l,(l+r)/2,v*2),mx(pocz,kon,(l+r)/2+1,r,v*2+1));
}
void dfs(ll v,ll pop,ll dpth){
    pre[v]=ak;
    kto[ak]=v;
    dpt[v]=dpth;
    pier[v]=pth.size();
    pth.pb(ak);
    
    ak++;
    for(ll i : g[v]){
        if(i==pop)continue;
        d[v].pb(i);
        dfs(i,v,dpth+1);
        pth.pb(pre[v]);
    }
    mxpre[v]=ak-1;
}
ll lca(ll a,ll b){
    a=pier[a];b=pier[b];
    if(a>b)swap(a,b);
    ll pom=log2(b-a+1);
    return kto[min(mn[a][pom],mn[b-(1<<pom)+1][pom])];
}
void zero(ll v){
    if(sgtree[POT/2+pre[v]].ff==0)return;
    sgtree[POT/2+pre[v]]={0,0};
    upd((POT/2+pre[v])/2);
    for(ll i : d[v])zero(i);
}
ll policz(ll v){
    pair<ll,ll> pom=mx(pre[v]+1,mxpre[v]+1,1,POT/2,1);
    if(pom.ff==0)return 0;
    ll nw=pom.ss;
    ll bst=0;
    for(ll i : d[nw]){
        if(sgtree[POT/2+pre[i]].ff==0)continue;
        ll p=mx(pre[i]+1,mxpre[i]+1,1,POT/2,1).ss;
        bst=max(bst,policz(i)-2*dpt[lca(p,nw)]+dpt[p]+dpt[nw]);
    }
    zero(nw);
    if(nw!=v){
    ll p=mx(pre[v]+1,mxpre[v]+1,1,POT/2,1).ss;
    bst=max(bst,policz(v)-2*dpt[lca(p,nw)]+dpt[p]+dpt[nw]);}
    return bst;
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(ll i=1;i<=n;i++){cin>>wys[i];gdzie[wys[i]]=i;}
    for(ll i=1;i<n;i++){
        cin>>a>>b;
        g[a].pb(b);
        g[b].pb(a);
    }
    dfs(1,-1,0);
    for(ll i=0;i<pth.size();i++)mn[i][0]=pth[i];
    for(ll j=1;j<20;j++){
        for(ll i=0;i+(1<<j)-1<pth.size();i++){
            mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
        }
    }
    for(ll i=0;i<n;i++){
        sgtree[POT/2+i]={wys[kto[i]],kto[i]};
        upd((POT/2+i)/2);
    }
    cout<<policz(1);
    return 0;
}

• 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