Submission #1038030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038030		juicy	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	156 ms	47460 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5, LG = 18;

int n;
int a[N], lab[N], top[N], dep[N], pr[LG][N];
long long dp[N];
vector<int> g[N];

void dfs(int u) {
  for (int v : g[u]) {
    if (v != pr[0][u]) {
      pr[0][v] = u;
      for (int j = 1; j < LG; ++j) {
        pr[j][v] = pr[j - 1][pr[j - 1][v]];
      }
      dep[v] = dep[u] + 1; 
      dfs(v);
    }
  }
}

int lca(int u, int v) {
  if (dep[u] < dep[v]) {
    swap(u, v);
  }
  for (int j = LG - 1; ~j; --j) {
    if (dep[u] - (1 << j) >= dep[v]) {
      u = pr[j][u];
    }
  }
  if (u == v) {
    return u;
  }
  for (int j = LG - 1; ~j; --j) {
    if (pr[j][u] != pr[j][v]) {
      u = pr[j][u], v = pr[j][v];
    }
  }
  return pr[0][u];
}

int dis(int u, int v) {
  return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

int find(int u) {
  return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}

void mrg(int u, int v) {
  u = find(u), v = find(v);
  if (lab[u] > lab[v]) {
    swap(u, v);
    swap(top[u], top[v]);
  }
  lab[u] += lab[v];
  lab[v] = u;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1);
  vector<int> ord(n); iota(ord.begin(), ord.end(), 1);
  sort(ord.begin(), ord.end(), [&](int i, int j) {
    return a[i] < a[j];
  });
  iota(top + 1, top + n + 1, 1);
  fill(lab + 1, lab + n + 1, -1);
  for (int u : ord) {
    for (int v : g[u]) {
      if (a[v] < a[u]) {
        auto x = top[find(v)];
        dp[u] = max(dp[u], dp[x] + dis(x, u));
        mrg(u, v);
      }
    }
  }
  cout << dp[ord.back()];
  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