Submission #932995

#	Time	Username	Problem	Language	Result	Execution time	Memory
932995		sheldon	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	321 ms	64108 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int nax = 2e5 + 5;

int height[nax], who[nax], up[nax][19], leader[nax], depth[nax];
long long dp[nax];

vector<int> edges[nax];



struct S  {
    vector<int> members;
    int mx = 0;
};

S comp[nax];


void dfs (int u, int p) {
    up[u][0] = p;
    depth[u] = depth[p] + 1;
    for (int i = 1; i < 19; ++i) {
        up[u][i] = up[up[u][i - 1]][i - 1];
    }
    for (int v : edges[u]) {
        if (v != p) {
            dfs (v, u);
        }
    }
}

int get_dist (int x, int y) {
    if (depth[x] < depth[y]) {
        swap(x, y);
    }
    int diff = depth[x] - depth[y];
    int ans = diff;
    for (int i = 0; i < 19; ++i) {
        if (diff & (1 << i)) {
            x = up[x][i];
        }
    }
    if (x == y) {
        return ans;
    }

    for (int i = 18; i >= 0; --i) {
        if (up[x][i] != up[y][i]) {
            ans += (1 << (i + 1));
            x = up[x][i];
            y = up[y][i];
        }
    }

    return ans + 2;
}

void merge (int u, int v) {
    u = leader[u];
    v = leader[v];
    if (u == v) {
        return;
    }

    if (comp[u].members.size() > comp[v].members.size()) {
        swap (u, v);
    }

    comp[v].mx = max(comp[v].mx, comp[u].mx);
    for (int x : comp[u].members) {
        leader[x] = v;
        comp[v].members.push_back(x);
    }
}

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> height[i];
        who[height[i]] = i;
        leader[i] = i;
        comp[i].members.push_back(i);
        comp[i].mx = height[i];
    }
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    dfs (1, 0);

    // cout << get_dist (2, 3) << '\n';
    for (int i = 1; i <= n; ++i) {
        int u = who[i];
        for (int v : edges[u]) {
            if (height[v] < i) {
                int me = leader[u], him = leader[v];
                dp[i] = max(dp[i], get_dist(u, who[comp[him].mx]) + dp[comp[him].mx]);
                merge (u, v);
            }
        }
    }
    cout << dp[n];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:103:21: warning: unused variable 'me' [-Wunused-variable]
  103 |                 int me = leader[u], him = leader[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