Submission #1245526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245526		hainam2k9	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	112 ms	46432 KiB

Main

#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 2e5+5;
const string NAME = "";
int n,a[MAXN],p[MAXN];
int depth[MAXN],par[MAXN][20];
ll dp[MAXN];
vector<int> adj[MAXN];
void dfs(int u){
    for(int& v : adj[u]){
        if(v==par[u][0]) continue;
        depth[v]=depth[u]+1, par[v][0]=u;
        for(int i = 1; i<=__lg(n); ++i)
            par[v][i]=par[par[v][i-1]][i-1];
        dfs(v);
    }
}
inline int lift(int x, int k){
    for(int i = 0; i<=__lg(n); ++i)
        if((k>>i)&1) x=par[x][i];
    return x;
}
int LCA(int x, int y){
    if(depth[x]!=depth[y]){
        if(depth[x]<depth[y]) swap(x,y);
        x=lift(x,depth[x]-depth[y]);
    }
    if(x==y) return x;
    for(int i = __lg(n); i>=0; --i)
        if(par[x][i]!=par[y][i]) x=par[x][i], y=par[y][i];
    return par[x][0];
}
inline int dist(int x, int y){
    return depth[x]+depth[y]-2*depth[LCA(x,y)];
}
int Find(int u){
    if(u==p[u]) return u;
    return p[u]=Find(p[u]);
}
int main()
{
    tt;
    if(fopen((NAME + ".INP").c_str(), "r")) fo;
    cin >> n;
    for(int i = 1; i<=n; ++i)
        cin >> a[i];
    for(int i = 1; i<n; ++i){
        int x,y;
        cin >> x >> y;
        x=a[x], y=a[y];
        adj[x].pb(y), adj[y].pb(x);
    }
    dfs(1);
    iota(p+1,p+n+1,1);
    for(int i = 1; i<=n; ++i)
        for(int& j : adj[i]){
            if(j>i) continue;
            int u=Find(i), v=Find(j);
            dp[u]=max(dp[u],dp[v]+dist(u,v));
            p[v]=u;
        }
    cout << dp[n];
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:3:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:60:45: note: in expansion of macro 'fo'
   60 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~
Main.cpp:3:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |                                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:60:45: note: in expansion of macro 'fo'
   60 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~

• 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