Submission #1223850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223850		minhpk	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	344 ms	85032 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a;
int pos[1000005];
int t[1000005];
vector <int> z[1000005];
int par[200001][21];
int par1[1000005];
int sz[1000005];
int dp[1000005];
int high[1000005];
void dfs(int i,int parent){
    for (auto p:z[i]){
        if (p==parent){
            continue;
        }
        high[p]=high[i]+1;
        par[p][0]=i;
        dfs(p,i);
    }
}
int lca(int x,int y){
    if (high[x]<high[y]){
        swap(x,y);
    }
    for (int i=20;i>=0;i--){
        if (high[par[x][i]]>=high[y]){
            x=par[x][i];
        }
    }
    if (x==y){
        return x;
    }
    for (int i=20;i>=0;i--){
         if (par[x][i]!=par[y][i] && par[x][i]){
             x=par[x][i];
             y=par[y][i];
         }
    }
    return par[x][0];
}
int find(int u){
    if (par1[u]==u) return u;
    return par1[u]=find(par1[u]);
}
void join(int x,int y){
    x=find(x);
    y=find(y);
    if (x==y) return;
    par1[y]=x;
    sz[x]+=sz[y];
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a;
    for (int i=1;i<=a;i++){
         int x;
         cin >> x;
         pos[x]=i;
         t[i]=x;
    }
    for (int i=1;i<a;i++){
         int x,y;
         cin >> x >> y;
         z[x].push_back(y);
         z[y].push_back(x);
    }
    high[0]=-1;
    dfs(1,0);
    for (int j=1;j<=20;j++){
         for (int i=1;i<=a;i++){
              par[i][j]=par[par[i][j-1]][j-1];
         }
    }
    for (int i=1;i<=a;i++){
         par1[i]=i;
         sz[i]=1;
    }
    for (int i=1;i<=a;i++){
         int u=pos[i];
         for (auto p:z[u]){
              if (t[p]<t[u]){
                  p=find(p);
                  int dist=high[p]+high[u]-2*high[lca(u,p)];
                  dp[u]=max(dp[u],dp[p]+dist);
                  join(u,p);
              }
         }
    }
    cout << dp[pos[a]] << "\n";
    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