oj.uz

Submission #837988

# Submission time Handle Problem Language Result Execution time Memory
837988 2023-08-26T03:06:11 Z gun_gan Cat Exercise (JOI23_ho_t4) C++17
54 / 100
 195 ms 64304 KB 
#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.0 / 7.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9736 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 4 ms 9684 KB Output is correct
11 Correct 5 ms 9812 KB Output is correct
12 Correct 5 ms 9812 KB Output is correct
13 Correct 5 ms 9812 KB Output is correct
14 Correct 5 ms 9812 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Correct 6 ms 9804 KB Output is correct
17 Correct 6 ms 9812 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9736 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 4 ms 9684 KB Output is correct
11 Correct 5 ms 9812 KB Output is correct
12 Correct 5 ms 9812 KB Output is correct
13 Correct 5 ms 9812 KB Output is correct
14 Correct 5 ms 9812 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Correct 6 ms 9804 KB Output is correct
17 Correct 6 ms 9812 KB Output is correct
18 Correct 8 ms 11092 KB Output is correct
19 Correct 8 ms 11024 KB Output is correct
20 Correct 7 ms 11092 KB Output is correct
21 Correct 8 ms 11092 KB Output is correct
22 Correct 8 ms 11092 KB Output is correct
23 Correct 8 ms 11092 KB Output is correct
24 Correct 8 ms 11092 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9736 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 4 ms 9684 KB Output is correct
11 Correct 5 ms 9812 KB Output is correct
12 Correct 5 ms 9812 KB Output is correct
13 Correct 5 ms 9812 KB Output is correct
14 Correct 5 ms 9812 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Correct 6 ms 9804 KB Output is correct
17 Correct 6 ms 9812 KB Output is correct
18 Correct 8 ms 11092 KB Output is correct
19 Correct 8 ms 11024 KB Output is correct
20 Correct 7 ms 11092 KB Output is correct
21 Correct 8 ms 11092 KB Output is correct
22 Correct 8 ms 11092 KB Output is correct
23 Correct 8 ms 11092 KB Output is correct
24 Correct 8 ms 11092 KB Output is correct
25 Correct 6 ms 9684 KB Output is correct
26 Correct 9 ms 10964 KB Output is correct
27 Correct 8 ms 10964 KB Output is correct
28 Correct 8 ms 10896 KB Output is correct
29 Correct 8 ms 10964 KB Output is correct
30 Correct 8 ms 10708 KB Output is correct
31 Correct 8 ms 10708 KB Output is correct
32 Correct 8 ms 10772 KB Output is correct
33 Correct 8 ms 10708 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9736 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 4 ms 9684 KB Output is correct
11 Correct 5 ms 9812 KB Output is correct
12 Correct 5 ms 9812 KB Output is correct
13 Correct 5 ms 9812 KB Output is correct
14 Correct 5 ms 9812 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Correct 6 ms 9804 KB Output is correct
17 Correct 6 ms 9812 KB Output is correct
18 Correct 8 ms 11092 KB Output is correct
19 Correct 8 ms 11024 KB Output is correct
20 Correct 7 ms 11092 KB Output is correct
21 Correct 8 ms 11092 KB Output is correct
22 Correct 8 ms 11092 KB Output is correct
23 Correct 8 ms 11092 KB Output is correct
24 Correct 8 ms 11092 KB Output is correct
25 Incorrect 130 ms 64304 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 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 195 ms 52980 KB Output is correct
4 Correct 182 ms 52992 KB Output is correct
5 Correct 195 ms 52892 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 4 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 4 ms 9736 KB Output is correct
9 Correct 4 ms 9684 KB Output is correct
10 Correct 4 ms 9684 KB Output is correct
11 Correct 5 ms 9812 KB Output is correct
12 Correct 5 ms 9812 KB Output is correct
13 Correct 5 ms 9812 KB Output is correct
14 Correct 5 ms 9812 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Correct 6 ms 9804 KB Output is correct
17 Correct 6 ms 9812 KB Output is correct
18 Correct 8 ms 11092 KB Output is correct
19 Correct 8 ms 11024 KB Output is correct
20 Correct 7 ms 11092 KB Output is correct
21 Correct 8 ms 11092 KB Output is correct
22 Correct 8 ms 11092 KB Output is correct
23 Correct 8 ms 11092 KB Output is correct
24 Correct 8 ms 11092 KB Output is correct
25 Correct 6 ms 9684 KB Output is correct
26 Correct 9 ms 10964 KB Output is correct
27 Correct 8 ms 10964 KB Output is correct
28 Correct 8 ms 10896 KB Output is correct
29 Correct 8 ms 10964 KB Output is correct
30 Correct 8 ms 10708 KB Output is correct
31 Correct 8 ms 10708 KB Output is correct
32 Correct 8 ms 10772 KB Output is correct
33 Correct 8 ms 10708 KB Output is correct
34 Incorrect 130 ms 64304 KB Output isn't correct
35 Halted 0 ms 0 KB -