oj.uz

Submission #1038029

# Submission time Handle Problem Language Result Execution time Memory
1038029 2024-07-29T12:16:47 Z juicy Cat Exercise (JOI23_ho_t4) C++17
31 / 100
 10 ms 11412 KB 
#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e5 + 5, LG = 17;

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 1 ms 10844 KB Output is correct
6 Correct 1 ms 10912 KB Output is correct
7 Correct 1 ms 10844 KB Output is correct
8 Correct 1 ms 10840 KB Output is correct
9 Correct 1 ms 10840 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 1 ms 10844 KB Output is correct
6 Correct 1 ms 10912 KB Output is correct
7 Correct 1 ms 10844 KB Output is correct
8 Correct 1 ms 10840 KB Output is correct
9 Correct 1 ms 10840 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 1 ms 10856 KB Output is correct
13 Correct 1 ms 10844 KB Output is correct
14 Correct 1 ms 10844 KB Output is correct
15 Correct 1 ms 10892 KB Output is correct
16 Correct 1 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 1 ms 10844 KB Output is correct
6 Correct 1 ms 10912 KB Output is correct
7 Correct 1 ms 10844 KB Output is correct
8 Correct 1 ms 10840 KB Output is correct
9 Correct 1 ms 10840 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 1 ms 10856 KB Output is correct
13 Correct 1 ms 10844 KB Output is correct
14 Correct 1 ms 10844 KB Output is correct
15 Correct 1 ms 10892 KB Output is correct
16 Correct 1 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 3 ms 11352 KB Output is correct
19 Correct 4 ms 11412 KB Output is correct
20 Correct 3 ms 11356 KB Output is correct
21 Correct 3 ms 11356 KB Output is correct
22 Correct 3 ms 11356 KB Output is correct
23 Correct 4 ms 11356 KB Output is correct
24 Correct 3 ms 11260 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 1 ms 10844 KB Output is correct
6 Correct 1 ms 10912 KB Output is correct
7 Correct 1 ms 10844 KB Output is correct
8 Correct 1 ms 10840 KB Output is correct
9 Correct 1 ms 10840 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 1 ms 10856 KB Output is correct
13 Correct 1 ms 10844 KB Output is correct
14 Correct 1 ms 10844 KB Output is correct
15 Correct 1 ms 10892 KB Output is correct
16 Correct 1 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 3 ms 11352 KB Output is correct
19 Correct 4 ms 11412 KB Output is correct
20 Correct 3 ms 11356 KB Output is correct
21 Correct 3 ms 11356 KB Output is correct
22 Correct 3 ms 11356 KB Output is correct
23 Correct 4 ms 11356 KB Output is correct
24 Correct 3 ms 11260 KB Output is correct
25 Correct 2 ms 10892 KB Output is correct
26 Correct 3 ms 11236 KB Output is correct
27 Correct 4 ms 11356 KB Output is correct
28 Correct 4 ms 11100 KB Output is correct
29 Correct 4 ms 11356 KB Output is correct
30 Correct 4 ms 11100 KB Output is correct
31 Correct 3 ms 11100 KB Output is correct
32 Correct 3 ms 11156 KB Output is correct
33 Correct 3 ms 11100 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 1 ms 10844 KB Output is correct
6 Correct 1 ms 10912 KB Output is correct
7 Correct 1 ms 10844 KB Output is correct
8 Correct 1 ms 10840 KB Output is correct
9 Correct 1 ms 10840 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 1 ms 10856 KB Output is correct
13 Correct 1 ms 10844 KB Output is correct
14 Correct 1 ms 10844 KB Output is correct
15 Correct 1 ms 10892 KB Output is correct
16 Correct 1 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 3 ms 11352 KB Output is correct
19 Correct 4 ms 11412 KB Output is correct
20 Correct 3 ms 11356 KB Output is correct
21 Correct 3 ms 11356 KB Output is correct
22 Correct 3 ms 11356 KB Output is correct
23 Correct 4 ms 11356 KB Output is correct
24 Correct 3 ms 11260 KB Output is correct
25 Incorrect 6 ms 8028 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 2 ms 10904 KB Output is correct
3 Runtime error 10 ms 10896 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10844 KB Output is correct
2 Correct 1 ms 10844 KB Output is correct
3 Correct 1 ms 10844 KB Output is correct
4 Correct 1 ms 10844 KB Output is correct
5 Correct 1 ms 10844 KB Output is correct
6 Correct 1 ms 10912 KB Output is correct
7 Correct 1 ms 10844 KB Output is correct
8 Correct 1 ms 10840 KB Output is correct
9 Correct 1 ms 10840 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 1 ms 10856 KB Output is correct
13 Correct 1 ms 10844 KB Output is correct
14 Correct 1 ms 10844 KB Output is correct
15 Correct 1 ms 10892 KB Output is correct
16 Correct 1 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 3 ms 11352 KB Output is correct
19 Correct 4 ms 11412 KB Output is correct
20 Correct 3 ms 11356 KB Output is correct
21 Correct 3 ms 11356 KB Output is correct
22 Correct 3 ms 11356 KB Output is correct
23 Correct 4 ms 11356 KB Output is correct
24 Correct 3 ms 11260 KB Output is correct
25 Correct 2 ms 10892 KB Output is correct
26 Correct 3 ms 11236 KB Output is correct
27 Correct 4 ms 11356 KB Output is correct
28 Correct 4 ms 11100 KB Output is correct
29 Correct 4 ms 11356 KB Output is correct
30 Correct 4 ms 11100 KB Output is correct
31 Correct 3 ms 11100 KB Output is correct
32 Correct 3 ms 11156 KB Output is correct
33 Correct 3 ms 11100 KB Output is correct
34 Incorrect 6 ms 8028 KB Output isn't correct
35 Halted 0 ms 0 KB -