Submission #1225639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225639		TadijaSebez	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	195 ms	56672 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int N=200050;
const int L=20;
vector<int> E[N],G[N];
int dep[N],par[N][L];

void DFS(int u,int p){
    par[u][0]=p;
    for(int i=1;i<L;i++){
        par[u][i]=par[par[u][i-1]][i-1];
    }
    dep[u]=dep[p]+1;
    for(int v:E[u]){
        if(v!=p){
            DFS(v,u);
        }
    }
}
int LCA(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    for(int i=L-1;i>=0;i--)if(dep[par[u][i]]>=dep[v])u=par[u][i];
    for(int i=L-1;i>=0;i--)if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];
    return u==v?v:par[v][0];
}
int Dist(int u,int v){return dep[u]+dep[v]-2*dep[LCA(u,v)];}

ll dp[N],val[N];
void Solve(int u){
    for(int v:G[u]){
        Solve(v);
        dp[u]=max(dp[u],dp[v]+val[v]);
    }
}

struct DSU{
    int p[N];
    DSU(){}
    void init(int n){
        for(int i=1;i<=n;i++)p[i]=i;
    }
    int Find(int u){return p[u]==u?u:p[u]=Find(p[u]);}
    void Union(int u,int v){
        p[Find(u)]=Find(v);
    }
}DS;

int p[N],node[N];
int main(){
    int n;
    scanf("%i",&n);
    for(int i=1;i<=n;i++)scanf("%i",&p[i]),node[p[i]]=i;
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%i %i",&u,&v);
        E[u].pb(v);
        E[v].pb(u);
    }
    DFS(1,0);
    DS.init(n);
    for(int i=1;i<=n;i++){
        for(int j:E[node[i]]){
            if(p[j]<i){
                G[i].pb(DS.Find(p[j]));
                val[DS.Find(p[j])]=Dist(node[i],node[DS.Find(p[j])]);
                //printf("%i -> %i: %lld\n",i,DS.Find(p[j]),val[DS.Find(p[j])]);
                DS.Union(p[j],i);
            }
        }
    }
    Solve(n);
    printf("%lld\n",dp[n]);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
Main.cpp:55:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     for(int i=1;i<=n;i++)scanf("%i",&p[i]),node[p[i]]=i;
      |                          ~~~~~^~~~~~~~~~~~
Main.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf("%i %i",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~

• 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