Submission #837988

#	Time	Username	Problem	Language	Result	Execution time	Memory
837988		gun_gan	Cat Exercise (JOI23_ho_t4)	C++17	54 / 100	195 ms	64304 KiB

Main

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

const int MX = 2e5 + 5;

int N;
int P[MX];

vector<int> g[MX];
vector<pair<int,int>> e, h[MX];

int dep[MX], up[MX][22], tin[MX], tout[MX], timer = 1;

bool isAncestor(int u, int v) { // is u ancestor of v ?
      return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca(int u, int v) {
      if(isAncestor(u, v)) return u;
      if(isAncestor(v, u)) return v;
      for(int k = 21; k >= 0; k--) {
            if(!isAncestor(up[u][k], v) && up[u][k] != 0) {
                  u = up[u][k];
            }
      }
      return up[u][0];
}

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

void dfs(int v, int p) {
      up[v][0] = p;
      for(int k = 1; k < 22; k++) {
            up[v][k] = up[up[v][k - 1]][k - 1];
      }
      tin[v] = timer;
      for(auto u : g[v]) {
            if(u == p) continue;
            dep[u] = dep[v] + 1;
            dfs(u, v);            
      }
      tout[v] = timer++;
}

int par[MX];

int find(int v) {
      return par[v] == v ? v : par[v] = find(par[v]);
}

void merge(int u, int v) {
      u = find(u), v = find(v);
      par[v] = u;
}

void dfs2(int v, int p) {
      for(auto [u, w] : h[v]) {
            if(u == p) continue;
            dep[u] = dep[v] + w;
            dfs2(u, v);
      }
}

int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);

      cin >> N;
      for(int i = 1; i <= N; i++) cin >> P[i];
      for(int i = 0; i < N - 1; i++) {
            int a, b;
            cin >> a >> b;
            g[a].push_back(b);
            g[b].push_back(a);
            e.push_back({a, b});
      }

      dfs(1, 0);

      vector<int> ord;
      for(int i = 1; i <= N; i++) ord.push_back(i);

      sort(ord.begin(), ord.end(), [&](auto i, auto j) {
            return P[i] < P[j];
      });

      vector<array<int,3>> newEdges;

      for(int i = 1; i <= N; i++) par[i] = i;

      for(auto x : ord) {
            for(auto v : g[x]) {
                  if(P[v] < P[x]) {
                        newEdges.push_back({x, find(v), dist(x, find(v))});
                        merge(x, v);
                  }
            }
      }

      for(int i = 1; i <= N; i++) dep[i] = 0;

      for(auto [u, v, w] : newEdges) {
            // cout << u << " " << v << " " << w << '\n';
            h[u].push_back({v, w});
            h[v].push_back({u, w});
      }

      for(int i = 1; i <= N; i++) {
            if(P[i] == N) {
                  dfs2(i, 0);
                  break;
            }
      }

      cout << *max_element(dep, dep + N + 1) << '\n';
}

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