oj.uz

Submission #1028823

# Submission time Handle Problem Language Result Execution time Memory
1028823 2024-07-20T09:12:33 Z NeroZein Cat Exercise (JOI23_ho_t4) C++17
30 / 100
 167 ms 54356 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int LOG = 18;
const int N = 2e5 + 5; 

int a[N];
int dep[N];
int up[LOG][N];
bool active[N];
vector<int> g[N];
long long ans[N];
int p[N], sz[N], mx[N];

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

int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (int j = 0; j < LOG; ++j) {
    if ((dep[u] - dep[v]) >> j & 1) {
      u = up[j][u];
    }
  }
  if (u == v) {
    return u;
  }
  for (int j = LOG - 1; j >= 0; --j) {
    if (up[j][u] != up[j][v]) {
      u = up[j][u]; 
      v = up[j][v];
    }
  }
  return up[0][u];
}

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

int get(int v) {
  return p[v] = (p[v] == v ? v : get(p[v]));
}

void unite(int u, int v) {
  u = get(u); v = get(v); 
  if (sz[u] > sz[v]) {
    swap(u, v);
  }
  p[u] = v;
  sz[v] += sz[u];
  int w = dist(mx[u], mx[v]);
  if (a[mx[v]] > a[mx[u]]) {
    ans[v] = max(ans[v], ans[u] + w);     
  } else {
    mx[v] = mx[u];
    ans[v] += w;
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for(int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1, 1); 
  vector<int> ord(n);
  iota(ord.begin(), ord.end(), 1);
  sort(ord.begin(), ord.end(), [&](int u, int v) {
    return a[u] < a[v];
  });
  for (int i = 1; i <= n; ++i) {
    p[i] = i;
    sz[i] = 1; 
    mx[i] = i; 
  }
  for (int v : ord) {
    for (int u : g[v]) {
      if (active[u]) {
        unite(u, v);        
      }
    }
    active[v] = true;
  }
  cout << ans[get(ord.back())] << '\n';
  return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 2 ms 5324 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5208 KB Output is correct
8 Correct 2 ms 5208 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 2 ms 5324 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5208 KB Output is correct
8 Correct 2 ms 5208 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 2 ms 5208 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 3 ms 5208 KB Output is correct
14 Incorrect 2 ms 5212 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 2 ms 5324 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5208 KB Output is correct
8 Correct 2 ms 5208 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 2 ms 5208 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 3 ms 5208 KB Output is correct
14 Incorrect 2 ms 5212 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 2 ms 5324 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5208 KB Output is correct
8 Correct 2 ms 5208 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 2 ms 5208 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 3 ms 5208 KB Output is correct
14 Incorrect 2 ms 5212 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 2 ms 5324 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5208 KB Output is correct
8 Correct 2 ms 5208 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 2 ms 5208 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 3 ms 5208 KB Output is correct
14 Incorrect 2 ms 5212 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 167 ms 54252 KB Output is correct
4 Correct 158 ms 54104 KB Output is correct
5 Correct 159 ms 54356 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 3 ms 5212 KB Output is correct
3 Correct 2 ms 5212 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 2 ms 5324 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5208 KB Output is correct
8 Correct 2 ms 5208 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 2 ms 5208 KB Output is correct
12 Correct 2 ms 5212 KB Output is correct
13 Correct 3 ms 5208 KB Output is correct
14 Incorrect 2 ms 5212 KB Output isn't correct
15 Halted 0 ms 0 KB -