Submission #1245286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245286		Geforgs	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	316 ms	72456 KiB

Main

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>
#include <stack>
#include <bit>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
#define ll long long
#define ld long double
#define inf (ll)(2*1e18)
#define sort(a) sort(a.begin(), a.end())
#define reverse(a) reverse(a.begin(), a.end())
#define pb push_back
#define endl "\n"
using namespace std;

const ll dim = 20;

void DFS(ll id, ll last, ll d, vector<vector<ll>>& a, vector<ll>& depth, vector<vector<ll>>& up){
    up[id][0] = last;
    depth[id] = d;
    for(int i=1;i<dim;++i){
        up[id][i] = up[up[id][i-1]][i-1];
    }
    for(auto el: a[id]){
        if(el == last) continue;
        DFS(el, id, d+1, a, depth, up);
    }
}

ll lca(ll x, ll y, vector<ll>& depth, vector<vector<ll>>& up){
    if(depth[x] < depth[y]) swap(x, y);
    for(int i=dim-1;i>=0;--i){
        if(depth[up[x][i]] >= depth[y]){
            x = up[x][i];
        }
    }
    if(x == y) return x;
    for(int i=dim-1;i>=0;--i){
        if(up[x][i] != up[y][i]){
            x = up[x][i];
            y = up[y][i];
        }
    }
    return up[x][0];
}

ll get(ll x, vector<ll>& parent){
    if(x == parent[x]) return x;
    return parent[x] = get(parent[x], parent);
}

ll dist(ll x, ll y, vector<vector<ll>>& up, vector<ll>& depth){
    ll w = lca(x, y, depth, up);
    return depth[x] + depth[y] - 2*depth[w];
}

void unite(ll x, ll y, vector<ll>& parent, vector<vector<ll>>& up, vector<ll>& depth, vector<ll>& dp){
    x = get(x, parent);
    y = get(y, parent);
    parent[x] = y;
    dp[y] = max(dp[y], dp[x] + dist(x, y, up, depth));
}

void solve(){
    ll n, i, x, y;
    cin>>n;
    vector<vector<ll>> a(n);
    vector<vector<ll>> up(n, vector<ll>(dim));
    vector<ll> depth(n);
    vector<ll> p(n);
    vector<ll> parent(n);
    vector<ll> dp(n);
    for(i=0;i<n;++i){
        cin>>p[i];
        --p[i];
        parent[i] = i;
    }
    for(i=1;i<n;++i){
        cin>>x>>y;
        --x;
        --y;
        x = p[x];
        y = p[y];
        a[x].pb(y);
        a[y].pb(x);
    }
    DFS(0, 0, 0, a, depth, up);
    for(i=0;i<n;++i){
        for(auto el: a[i]){
            if(el < i){
                unite(el, i, parent, up, depth, dp);
            }
        }
    }
    cout<<dp[n-1]<<endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    srand(time(nullptr));
    ll t=1;
//    cin>>t;
    for(;t>0;--t){
        solve();
    }
    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