oj.uz

Submission #828049

# Submission time Handle Problem Language Result Execution time Memory
828049 2023-08-17T02:36:36 Z null_awe Cat Exercise (JOI23_ho_t4) C++14
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
using namespace std;

struct DSU {

  vector<int> r, p, h;

  DSU() {}

  DSU(int n, vector<int> h) : r(n), p(n), h(h.begin(), h.end()) {
    for (int i = 0; i < n; ++i) p[i] = i;
  }

  int find(int a) { return a == p[a] ? a : p[a] = find(p[a]); }

  void link(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
    if (r[a] < r[b]) swap(a, b);
    if (r[a] == r[b]) ++r[a];
    p[b] = a, h[a] = max(h[a], h[b]);
  }
};

struct LCA {

  vector<vector<int>> adj;
  vector<int> depths;
  int n;
  vector<vector<int>> up;

  LCA() {}

  LCA(int n, vector<vector<int>> _adj) : n(n) {
    adj = _adj;
    depths.resize(n);
    up = vector<vector<int>>(n, vector<int>(20));
  }

  void dfs(int v, int p, int d) {
    depths[v] = d, up[v][0] = p;
    for (int u : adj[v]) if (u != p) dfs(u, v, d + 1);
  }

  void init() {
    dfs(0, 0, 0);
    for (int j = 1; j < 20; ++j) for (int i = 0; i < n; ++i) up[i][j] = up[up[i][j - 1]][j - 1];
  }

  int jmp(int a, int u) {
    for (int i = 0; i < 20; ++i) if (u & (1 << i)) a = up[a][i];
    return a;
  }

  int lca(int a, int b) {
    if (depths[a] > depths[b]) swap(a, b);
    b = jmp(b, depths[a] - depths[b]);
    for (int i = 19; i >= 0; --i) if (up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];
    return a != b ? up[a][0] : a;
  }

  int dist(int a, int b) {
    // cout << depths[a] << ' ' << depths[b] << ' ' << 2 * depths[lca(a, b)] << endl;
    return depths[a] + depths[b] - 2 * depths[lca(a, b)];
  }
};

int main() {
  int n; cin >> n;
  vector<int> h(n); for (int i = 0; i < n; ++i) cin >> h[i];
  for (int i = 0; i < n; ++i) --h[i];
  vector<vector<int>> adj(n);
  for (int i = 0; i < n - 1; ++i) {
    int a, b; cin >> a >> b; --a, --b;
    a = h[a], b = h[b];
    adj[a].push_back(b); adj[b].push_back(a);
  }
  DSU dsu(n, h);
  LCA lca(n, adj); lca.init();
  vector<long long> dp(n);
  for (int i = 0; i < n; ++i) {
    // cout << i << endl;
    for (int u : adj[i]) {
      if (u > i) continue;
      int ru = dsu.h[dsu.find(u)];
      dp[i] = max(dp[i], lca.dist(i, ru) + dp[ru]);
    }
  }
  cout << dp[n - 1] << '\n';
  return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -