Submission #786587

#	Time	Username	Problem	Language	Result	Execution time	Memory
786587		tch1cherin	Cat Exercise (JOI23_ho_t4)	C++17	31 / 100	2069 ms	29920 KiB

Main

#include <bits/stdc++.h>
using namespace std;

vector<int> P, D, Max;
vector<bool> used;
vector<vector<int>> G;

void DFS(int u, int p) {
  Max[u] = u;
  for (int v : G[u]) {
    if (v != p && !used[v]) {
      D[v] = D[u] + 1;
      DFS(v, u);
      if (P[Max[v]] > P[Max[u]]) {
        Max[u] = Max[v];
      }
    }
  }
}

int solve(int u) {
  D[u] = 0;
  DFS(u, -1);
  used[u] = true;
  int ans = 0;
  for (int v : G[u]) {
    if (!used[v]) {
      int dist = D[Max[v]];
      ans = max(ans, dist + solve(Max[v]));
    }
  }
  return ans;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N;
  cin >> N;
  P = D = Max = vector<int>(N);
  G.resize(N);
  used.resize(N);
  for (int &v : P) {
    cin >> v;
  }
  for (int i = 0; i < N - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  for (int i = 0; i < N; i++) {
    if (P[i] == N) {
      cout << solve(i) << "\n"; 
    }
  }
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26