Submission #797865

#	Time	Username	Problem	Language	Result	Execution time	Memory
797865		1bin	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	210 ms	61852 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 2e5 + 5;
ll n, h[NMAX], a, b, lv[NMAX], p[NMAX][18], par[NMAX], dp[NMAX];
vector<int> adj[NMAX];
int find(int x){return par[x] == -1 ? x : par[x] = find(par[x]);}

void dfs(int x, int par){
    for(int& nx : adj[x]){
        if(nx == par) continue;
        p[nx][0] = x;
        lv[nx] = lv[x] + 1;
        dfs(nx, x);
    }    
    return;
}

int dist(int a, int b){
    int ret = 0;
    if(lv[a] < lv[b]) swap(a, b);
    for(int i = 17; i >= 0; i--)
        if(lv[a] - lv[b] >= 1 << i){
            a = p[a][i];
            ret += 1 << i;
        }
    if(a == b) return ret;
    for(int i = 17; i >= 0; i--)
        if(p[a][i] != p[b][i]){
            a = p[a][i];
            b = p[b][i];
            ret += 1 << (i + 1);
        }
    return ret + 2;
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = 1; i < n; i++){
        cin >> a >> b;
        adj[h[a]].emplace_back(h[b]);
        adj[h[b]].emplace_back(h[a]);
    }
    dfs(1, -1);
    for(int j = 1; j < 18; j++)
        for(int i = 1; i <= n; i++)
            p[i][j] = p[p[i][j - 1]][j - 1];
    memset(par, -1, sizeof(par));
    for(int i = 1; i <= n; i++){
        for(int j : adj[i]){
            j = find(j);
            if(j > i) continue;
            dp[i] = max(dp[i], dp[j] + dist(i, j));
            par[j] = i;
        }
    }
    cout << dp[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