oj.uz

Submission #792226

# Submission time Handle Problem Language Result Execution time Memory
792226 2023-07-24T19:31:29 Z WLZ Cat Exercise (JOI23_ho_t4) C++17
54 / 100
 151 ms 61340 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include "templates/debug.h"
#else
#define debug(...) 0
#endif

#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define eb emplace_back
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int) x.size()

using ll = long long;
using ull = unsigned ll;
using lll = __int128_t;
using ulll = __uint128_t;
using ld = long double;
using ii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
template<typename T> using mx_pq = priority_queue<T>;
template<typename T> using mn_pq = priority_queue<T, vector<T>, greater<T>>;

template<typename T> void cmax(T &a, const T &b) { a = max(a, b); }
template<typename T> void cmin(T &a, const T &b) { a = min(a, b); }

const int INF = 0x3f3f3f3f;
const ll LINF = (ll) 1e18;
const double DINF = 1.0 / 0.0;
const double pi = acos(-1);
const double EPS = 1e-9;

void solve(int current_case);

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  //cin >> t;
  for (int q = 1; q <= t; q++) solve(q);
  return 0;
}

class least_common_ancestor {
  private:
    int n;
    vector<vi> g;
    vi p, jump, d;

    void dfs(int u) {
      if (d[p[u]] - d[jump[p[u]]] == d[jump[p[u]]] - d[jump[jump[p[u]]]]) jump[u] = jump[jump[p[u]]];
      else jump[u] = p[u];
      for (auto &v : g[u]) {
        if (v != p[u]) {
          d[v] = d[u] + 1;
          p[v] = u;
          dfs(v);
        }
      }
    }
  public:
    least_common_ancestor(const vector<vi> &_g, int root = 1) : g(_g) {
      n = SZ(g);
      p.resize(n); jump.resize(n); d.resize(n);
      p[root] = root; jump[root] = root; d[root] = 0;
      dfs(root);
    }
  
    int kth_ancestor(int u, int k) {
      int v = u;
      while (d[v] > d[u] - k) {
        if (d[jump[v]] >= d[u] - k) v = jump[v];
        else v = p[v];
      }
      return v;
    }

    int query(int u, int v) {
      if (d[u] < d[v]) swap(u, v);
      u = kth_ancestor(u, d[u] - d[v]);
      if (u == v) return u;
      while (p[u] != p[v]) {
        if (jump[u] != jump[v]) u = jump[u], v = jump[v];
        else u = p[u], v = p[v];
      }
      return p[u];
    }

    int depth(int u) {
      return d[u];
    }

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

class dsu {
  private: vector<int> p, rank, a, mx;
  public:
    dsu(const vector<int> &_a) : a(_a) {
      int n = SZ(a);
      mx.resize(n);
      iota(all(mx), 0);
      p.assign(n, -1);
      rank.assign(n, 0);
    }

    int root(int x) {
      if (p[x] == -1) return x;
      return p[x] = root(p[x]);
    }

    bool connected(int x, int y) {
      return root(x) == root(y);
    }

    void connect(int x, int y) {
      x = root(x); y = root(y);
      if (x != y) {
        if (rank[x] > rank[y]) {
          p[y] = x;
          if (a[mx[y]] > a[mx[x]]) mx[x] = mx[y];
        }
        else {
          p[x] = y;
          if (a[mx[x]] > a[mx[y]]) mx[y] = mx[x];
          if (rank[x] == rank[y]) rank[y]++;
        }
      }
    }

    int max(int x) {
      return mx[root(x)];
    }
};

int n;
vector<vi> g, g2;
vi h;

int dfs(int u, least_common_ancestor &lca) {
  int ans = 0;
  for (auto &v : g2[u]) cmax(ans, lca.dist(u, v) + dfs(v, lca));
  return ans;
}

void solve(int current_case) {
  cin >> n;
  g.resize(n + 1);
  h.resize(n + 1);
  vii b;
  rep(i, 1, n + 1) cin >> h[i], b.eb(h[i], i);
  rep(i, 1, n) {
    int a, b; cin >> a >> b;
    g[a].pb(b); g[b].pb(a);
  }
  sort(all(b));
  vi used(n + 1, 0);
  g2.resize(n + 1);
  dsu uf(h);
  for (auto &p : b) {
    int u = p.second;
    used[u] = 1;
    for (auto &v : g[u]) if (used[v]) g2[u].pb(uf.max(v));
    for (auto &v : g[u]) if (used[v]) uf.connect(u, v);
  }
  least_common_ancestor lca(g, b[n - 1].second);
  cout << dfs(b[n - 1].second, lca) << '\n';
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 3 ms 1744 KB Output is correct
19 Correct 3 ms 1728 KB Output is correct
20 Correct 3 ms 1748 KB Output is correct
21 Correct 3 ms 1480 KB Output is correct
22 Correct 3 ms 1456 KB Output is correct
23 Correct 3 ms 1364 KB Output is correct
24 Correct 3 ms 1364 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 3 ms 1744 KB Output is correct
19 Correct 3 ms 1728 KB Output is correct
20 Correct 3 ms 1748 KB Output is correct
21 Correct 3 ms 1480 KB Output is correct
22 Correct 3 ms 1456 KB Output is correct
23 Correct 3 ms 1364 KB Output is correct
24 Correct 3 ms 1364 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 3 ms 1620 KB Output is correct
27 Correct 3 ms 1620 KB Output is correct
28 Correct 3 ms 1620 KB Output is correct
29 Correct 3 ms 1620 KB Output is correct
30 Correct 3 ms 1364 KB Output is correct
31 Correct 3 ms 1364 KB Output is correct
32 Correct 5 ms 1364 KB Output is correct
33 Correct 4 ms 1364 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 3 ms 1744 KB Output is correct
19 Correct 3 ms 1728 KB Output is correct
20 Correct 3 ms 1748 KB Output is correct
21 Correct 3 ms 1480 KB Output is correct
22 Correct 3 ms 1456 KB Output is correct
23 Correct 3 ms 1364 KB Output is correct
24 Correct 3 ms 1364 KB Output is correct
25 Incorrect 142 ms 61340 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 148 ms 44312 KB Output is correct
4 Correct 147 ms 44428 KB Output is correct
5 Correct 151 ms 44196 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 320 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 3 ms 1744 KB Output is correct
19 Correct 3 ms 1728 KB Output is correct
20 Correct 3 ms 1748 KB Output is correct
21 Correct 3 ms 1480 KB Output is correct
22 Correct 3 ms 1456 KB Output is correct
23 Correct 3 ms 1364 KB Output is correct
24 Correct 3 ms 1364 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 3 ms 1620 KB Output is correct
27 Correct 3 ms 1620 KB Output is correct
28 Correct 3 ms 1620 KB Output is correct
29 Correct 3 ms 1620 KB Output is correct
30 Correct 3 ms 1364 KB Output is correct
31 Correct 3 ms 1364 KB Output is correct
32 Correct 5 ms 1364 KB Output is correct
33 Correct 4 ms 1364 KB Output is correct
34 Incorrect 142 ms 61340 KB Output isn't correct
35 Halted 0 ms 0 KB -