oj.uz

Submission #786737

# Submission time Handle Problem Language Result Execution time Memory
786737 2023-07-18T12:13:53 Z tch1cherin Cat Exercise (JOI23_ho_t4) C++17
0 / 100
 1811 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 2e5 + 5;
const int MAX_L = __lg(MAX_N) + 1;
bitset<MAX_N> used_c, used_s;
unordered_map<int, int> pos[MAX_N];
set<pair<int, int>> values[MAX_N];
vector<int> graph[MAX_N], parent[MAX_N], dist[MAX_N];
vector<bool> 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, int& t) {
  pos[c][u] = t;
  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, ++t);
    } 
  }
}

void centroid(int u) {
  find_sizes(u, -1);
  int t = 0;
  DFS(u, u, -1, 0, t);
  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][u] = true;
  for (int v : graph[u]) {
    if (v != p && pos[c].count(v) && !deleted[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);
  }
  centroid(find_centroid(0, -1, N));
  for (int i = 0; i < N; i++) {
    if (value[i] == N) {
      cout << solve(i) << "\n";
    }
  }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42592 KB Output is correct
2 Runtime error 1178 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42592 KB Output is correct
2 Runtime error 1178 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42592 KB Output is correct
2 Runtime error 1178 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42592 KB Output is correct
2 Runtime error 1178 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42592 KB Output is correct
2 Runtime error 1178 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 42552 KB Output is correct
2 Runtime error 1811 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42592 KB Output is correct
2 Runtime error 1178 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -