oj.uz

Submission #786829

# Submission time Handle Problem Language Result Execution time Memory
786829 2023-07-18T13:21:12 Z tch1cherin Cat Exercise (JOI23_ho_t4) C++17
51 / 100
 2000 ms 427340 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

struct custom_hash {
  size_t operator()(uint64_t x) const {
    return (x + 228) * 239;
  }
};

const int MAX_N = 2e5 + 5;
const int MAX_L = __lg(MAX_N) + 1;
bitset<MAX_N> used_c, used_s;
gp_hash_table<int, int> pos[MAX_N];
set<pair<int, int>> values[MAX_N];
vector<int> graph[MAX_N], parent[MAX_N], dist[MAX_N];
vector<char> deleted[MAX_N]; 
int ancestors[MAX_N][MAX_L], num[MAX_N] = {}, value[MAX_N], sz[MAX_N];

void find_sizes(int u, int p) {
  sz[u] = 1;
  for (int v : graph[u]) {
    if (v != p && !used_c[v]) {
      find_sizes(v, u);
      sz[u] += sz[v];
    }
  }
}

int find_centroid(int u, int p, int n) {
  for (int v : graph[u]) {
    if (v != p && !used_c[v] && sz[v] > n / 2) {
      return find_centroid(v, u, n);
    }
  }
  return u;
}

void DFS(int u, int c, int p, int d) {
  pos[c][u] = (int)dist[c].size();
  dist[c].push_back(d);
  parent[c].push_back(p);
  deleted[c].push_back(false);
  values[c].insert({value[u], u});
  ancestors[u][num[u]++] = c;
  for (int v : graph[u]) {
    if (v != p && !used_c[v]) {
      DFS(v, c, u, d + 1);
    } 
  }
}

void centroid(int u) {
  find_sizes(u, -1);
  DFS(u, u, -1, 0);
  used_c[u] = true;
  for (int v : graph[u]) {
    if (!used_c[v]) {
      centroid(find_centroid(v, u, sz[v]));
    }
  }
}

void delete_subtree(int u, int p, int c) {
  values[c].erase({value[u], u});
  deleted[c][pos[c][u]] = true;
  for (int v : graph[u]) {
    if (v != p && pos[c].find(v) != pos[c].end() && !deleted[c][pos[c][v]]) {
      delete_subtree(v, u, c);
    }
  }
}

int64_t solve(int u) {
  used_s[u] = true;
  int64_t ans = 0;
  for (int i = 0; i < num[u]; i++) {
    int A = ancestors[u][i];
    if (!deleted[A][pos[A][u]]) {
      delete_subtree(u, parent[A][pos[A][u]], A); 
    }
  }
  for (int v : graph[u]) {
    if (!used_s[v]) {
      tuple<int, int, int> val = {-1, -1, -1};
      for (int i = 0; i < num[v]; i++) {
        int A = ancestors[v][i];
        if (!deleted[A][pos[A][v]] && !values[A].empty()) {
          auto [valx, x] = *values[A].rbegin();
          val = max(val, {valx, -(dist[A][pos[A][x]] + dist[A][pos[A][v]]), x});
        }
      }
      ans = max(ans, solve(get<2>(val)) - get<1>(val) + 1);
    }
  }
  return ans;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N;
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> value[i];
  }
  for (int i = 0; i < N - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }
  find_sizes(0, -1);
  centroid(find_centroid(0, -1, N));
  for (int i = 0; i < N; i++) {
    if (value[i] == N) {
      cout << solve(i) << "\n";
    }
  }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 70764 KB Output is correct
2 Correct 42 ms 70788 KB Output is correct
3 Correct 53 ms 70768 KB Output is correct
4 Correct 44 ms 70792 KB Output is correct
5 Correct 43 ms 70712 KB Output is correct
6 Correct 44 ms 70740 KB Output is correct
7 Correct 44 ms 70732 KB Output is correct
8 Correct 43 ms 70740 KB Output is correct
9 Correct 52 ms 70788 KB Output is correct
10 Correct 43 ms 70704 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 70764 KB Output is correct
2 Correct 42 ms 70788 KB Output is correct
3 Correct 53 ms 70768 KB Output is correct
4 Correct 44 ms 70792 KB Output is correct
5 Correct 43 ms 70712 KB Output is correct
6 Correct 44 ms 70740 KB Output is correct
7 Correct 44 ms 70732 KB Output is correct
8 Correct 43 ms 70740 KB Output is correct
9 Correct 52 ms 70788 KB Output is correct
10 Correct 43 ms 70704 KB Output is correct
11 Correct 52 ms 71032 KB Output is correct
12 Correct 56 ms 71272 KB Output is correct
13 Correct 47 ms 71092 KB Output is correct
14 Correct 47 ms 70988 KB Output is correct
15 Correct 47 ms 71020 KB Output is correct
16 Correct 56 ms 71056 KB Output is correct
17 Correct 56 ms 71056 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 70764 KB Output is correct
2 Correct 42 ms 70788 KB Output is correct
3 Correct 53 ms 70768 KB Output is correct
4 Correct 44 ms 70792 KB Output is correct
5 Correct 43 ms 70712 KB Output is correct
6 Correct 44 ms 70740 KB Output is correct
7 Correct 44 ms 70732 KB Output is correct
8 Correct 43 ms 70740 KB Output is correct
9 Correct 52 ms 70788 KB Output is correct
10 Correct 43 ms 70704 KB Output is correct
11 Correct 52 ms 71032 KB Output is correct
12 Correct 56 ms 71272 KB Output is correct
13 Correct 47 ms 71092 KB Output is correct
14 Correct 47 ms 70988 KB Output is correct
15 Correct 47 ms 71020 KB Output is correct
16 Correct 56 ms 71056 KB Output is correct
17 Correct 56 ms 71056 KB Output is correct
18 Correct 62 ms 77784 KB Output is correct
19 Correct 65 ms 77704 KB Output is correct
20 Correct 67 ms 77756 KB Output is correct
21 Correct 67 ms 77388 KB Output is correct
22 Correct 66 ms 77392 KB Output is correct
23 Correct 67 ms 77412 KB Output is correct
24 Correct 78 ms 77392 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 70764 KB Output is correct
2 Correct 42 ms 70788 KB Output is correct
3 Correct 53 ms 70768 KB Output is correct
4 Correct 44 ms 70792 KB Output is correct
5 Correct 43 ms 70712 KB Output is correct
6 Correct 44 ms 70740 KB Output is correct
7 Correct 44 ms 70732 KB Output is correct
8 Correct 43 ms 70740 KB Output is correct
9 Correct 52 ms 70788 KB Output is correct
10 Correct 43 ms 70704 KB Output is correct
11 Correct 52 ms 71032 KB Output is correct
12 Correct 56 ms 71272 KB Output is correct
13 Correct 47 ms 71092 KB Output is correct
14 Correct 47 ms 70988 KB Output is correct
15 Correct 47 ms 71020 KB Output is correct
16 Correct 56 ms 71056 KB Output is correct
17 Correct 56 ms 71056 KB Output is correct
18 Correct 62 ms 77784 KB Output is correct
19 Correct 65 ms 77704 KB Output is correct
20 Correct 67 ms 77756 KB Output is correct
21 Correct 67 ms 77388 KB Output is correct
22 Correct 66 ms 77392 KB Output is correct
23 Correct 67 ms 77412 KB Output is correct
24 Correct 78 ms 77392 KB Output is correct
25 Correct 49 ms 70860 KB Output is correct
26 Correct 69 ms 77484 KB Output is correct
27 Correct 70 ms 77456 KB Output is correct
28 Correct 71 ms 77420 KB Output is correct
29 Correct 69 ms 77408 KB Output is correct
30 Correct 69 ms 75548 KB Output is correct
31 Correct 67 ms 75324 KB Output is correct
32 Correct 82 ms 75640 KB Output is correct
33 Correct 66 ms 75372 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 70764 KB Output is correct
2 Correct 42 ms 70788 KB Output is correct
3 Correct 53 ms 70768 KB Output is correct
4 Correct 44 ms 70792 KB Output is correct
5 Correct 43 ms 70712 KB Output is correct
6 Correct 44 ms 70740 KB Output is correct
7 Correct 44 ms 70732 KB Output is correct
8 Correct 43 ms 70740 KB Output is correct
9 Correct 52 ms 70788 KB Output is correct
10 Correct 43 ms 70704 KB Output is correct
11 Correct 52 ms 71032 KB Output is correct
12 Correct 56 ms 71272 KB Output is correct
13 Correct 47 ms 71092 KB Output is correct
14 Correct 47 ms 70988 KB Output is correct
15 Correct 47 ms 71020 KB Output is correct
16 Correct 56 ms 71056 KB Output is correct
17 Correct 56 ms 71056 KB Output is correct
18 Correct 62 ms 77784 KB Output is correct
19 Correct 65 ms 77704 KB Output is correct
20 Correct 67 ms 77756 KB Output is correct
21 Correct 67 ms 77388 KB Output is correct
22 Correct 66 ms 77392 KB Output is correct
23 Correct 67 ms 77412 KB Output is correct
24 Correct 78 ms 77392 KB Output is correct
25 Correct 1220 ms 427340 KB Output is correct
26 Correct 1295 ms 424560 KB Output is correct
27 Correct 1276 ms 424492 KB Output is correct
28 Correct 1564 ms 407020 KB Output is correct
29 Correct 1632 ms 407272 KB Output is correct
30 Correct 1630 ms 407064 KB Output is correct
31 Correct 1579 ms 407124 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 70708 KB Output is correct
2 Correct 45 ms 70804 KB Output is correct
3 Execution timed out 2106 ms 278612 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 70764 KB Output is correct
2 Correct 42 ms 70788 KB Output is correct
3 Correct 53 ms 70768 KB Output is correct
4 Correct 44 ms 70792 KB Output is correct
5 Correct 43 ms 70712 KB Output is correct
6 Correct 44 ms 70740 KB Output is correct
7 Correct 44 ms 70732 KB Output is correct
8 Correct 43 ms 70740 KB Output is correct
9 Correct 52 ms 70788 KB Output is correct
10 Correct 43 ms 70704 KB Output is correct
11 Correct 52 ms 71032 KB Output is correct
12 Correct 56 ms 71272 KB Output is correct
13 Correct 47 ms 71092 KB Output is correct
14 Correct 47 ms 70988 KB Output is correct
15 Correct 47 ms 71020 KB Output is correct
16 Correct 56 ms 71056 KB Output is correct
17 Correct 56 ms 71056 KB Output is correct
18 Correct 62 ms 77784 KB Output is correct
19 Correct 65 ms 77704 KB Output is correct
20 Correct 67 ms 77756 KB Output is correct
21 Correct 67 ms 77388 KB Output is correct
22 Correct 66 ms 77392 KB Output is correct
23 Correct 67 ms 77412 KB Output is correct
24 Correct 78 ms 77392 KB Output is correct
25 Correct 49 ms 70860 KB Output is correct
26 Correct 69 ms 77484 KB Output is correct
27 Correct 70 ms 77456 KB Output is correct
28 Correct 71 ms 77420 KB Output is correct
29 Correct 69 ms 77408 KB Output is correct
30 Correct 69 ms 75548 KB Output is correct
31 Correct 67 ms 75324 KB Output is correct
32 Correct 82 ms 75640 KB Output is correct
33 Correct 66 ms 75372 KB Output is correct
34 Correct 1220 ms 427340 KB Output is correct
35 Correct 1295 ms 424560 KB Output is correct
36 Correct 1276 ms 424492 KB Output is correct
37 Correct 1564 ms 407020 KB Output is correct
38 Correct 1632 ms 407272 KB Output is correct
39 Correct 1630 ms 407064 KB Output is correct
40 Correct 1579 ms 407124 KB Output is correct
41 Correct 41 ms 70708 KB Output is correct
42 Correct 45 ms 70804 KB Output is correct
43 Execution timed out 2106 ms 278612 KB Time limit exceeded
44 Halted 0 ms 0 KB -