Submission #1147229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147229		goduadzesaba	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	151 ms	63052 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,LOG=20,mod=1e9+7,inf=1e18;
int n,p[N],rp[N],x,y,d[N],dp[N],ans[N],tin[N],tout[N],l[N][LOG],cnt;
vector <int> v[N];
void dfs(int i,int p){
    tin[i]=++cnt; l[i][0]=p; dp[i]=dp[p]+1;
    for (int j=1; j<LOG; j++)
        l[i][j]=l[l[i][j-1]][j-1];
    for (int j:v[i]){
        if (j==p) continue;
        dfs(j,i);
    }
    tout[i]=cnt;
}
bool ispar(int a,int b){
    if (!a || (tin[a]<=tin[b] && tout[a]>=tout[b])) return 1;
    return 0;
}
int lca(int a,int b){
    if (ispar(a,b)) return a;
    for (int j=LOG-1; j>=0; j--)
        if (!ispar(l[a][j],b))
            a=l[a][j];
    return l[a][0];
}
int dist (int a,int b){
    return dp[a]+dp[b]-2*dp[lca(a,b)];
}
int par(int i){
    if (i==d[i]) return i;
    return d[i]=par(d[i]);
}
void make(int a,int b){
    a=par(a); b=par(b);
    if (a==b) return;
    if (p[a]<p[b]) swap(a,b);
    d[b]=a;
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n;
    for (int i=1; i<=n; i++) cin>>p[i],d[i]=i,rp[p[i]]=i;
    for (int i=1; i<n; i++){
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    for (int i=1; i<=n; i++){
        x=rp[i];
        for (int j:v[x]){
            if (p[j]>i) continue;    
            // cout << j << ' ' << i << ' ' << x << ' ' << par(j) << ' ' << dist(x, par(j)) << '\n';
            ans[x]=max(ans[x],dist(x,par(j))+ans[par(j)]);
            make(x,j);
        }
        // cout << "ans[x] = " << ans[x] << '\n';
    }
    cout<<ans[rp[n]];
}

• 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