oj.uz

Submission #837989

# Submission time Handle Problem Language Result Execution time Memory
837989 2023-08-26T03:06:52 Z gun_gan Cat Exercise (JOI23_ho_t4) C++17
100 / 100
 359 ms 85176 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX = 2e5 + 5;

int N;
int P[MX];

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

ll 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 4 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 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 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 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 4 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 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 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 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 5 ms 9812 KB Output is correct
16 Correct 5 ms 9812 KB Output is correct
17 Correct 5 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 4 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 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 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 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 5 ms 9812 KB Output is correct
16 Correct 5 ms 9812 KB Output is correct
17 Correct 5 ms 9812 KB Output is correct
18 Correct 8 ms 11476 KB Output is correct
19 Correct 7 ms 11476 KB Output is correct
20 Correct 7 ms 11476 KB Output is correct
21 Correct 8 ms 11476 KB Output is correct
22 Correct 8 ms 11476 KB Output is correct
23 Correct 11 ms 11588 KB Output is correct
24 Correct 8 ms 11476 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 4 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 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 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 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 5 ms 9812 KB Output is correct
16 Correct 5 ms 9812 KB Output is correct
17 Correct 5 ms 9812 KB Output is correct
18 Correct 8 ms 11476 KB Output is correct
19 Correct 7 ms 11476 KB Output is correct
20 Correct 7 ms 11476 KB Output is correct
21 Correct 8 ms 11476 KB Output is correct
22 Correct 8 ms 11476 KB Output is correct
23 Correct 11 ms 11588 KB Output is correct
24 Correct 8 ms 11476 KB Output is correct
25 Correct 6 ms 9684 KB Output is correct
26 Correct 8 ms 11348 KB Output is correct
27 Correct 8 ms 11348 KB Output is correct
28 Correct 9 ms 11348 KB Output is correct
29 Correct 8 ms 11348 KB Output is correct
30 Correct 8 ms 11220 KB Output is correct
31 Correct 9 ms 11220 KB Output is correct
32 Correct 8 ms 11220 KB Output is correct
33 Correct 8 ms 11220 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 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 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 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 5 ms 9812 KB Output is correct
16 Correct 5 ms 9812 KB Output is correct
17 Correct 5 ms 9812 KB Output is correct
18 Correct 8 ms 11476 KB Output is correct
19 Correct 7 ms 11476 KB Output is correct
20 Correct 7 ms 11476 KB Output is correct
21 Correct 8 ms 11476 KB Output is correct
22 Correct 8 ms 11476 KB Output is correct
23 Correct 11 ms 11588 KB Output is correct
24 Correct 8 ms 11476 KB Output is correct
25 Correct 151 ms 80084 KB Output is correct
26 Correct 145 ms 84148 KB Output is correct
27 Correct 141 ms 84192 KB Output is correct
28 Correct 187 ms 85176 KB Output is correct
29 Correct 222 ms 85164 KB Output is correct
30 Correct 185 ms 85168 KB Output is correct
31 Correct 246 ms 85112 KB Output is correct

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 9812 KB Output is correct
3 Correct 202 ms 68844 KB Output is correct
4 Correct 198 ms 68960 KB Output is correct
5 Correct 205 ms 68832 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 6 ms 9684 KB Output is correct
4 Correct 5 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 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 5 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 5 ms 9812 KB Output is correct
16 Correct 5 ms 9812 KB Output is correct
17 Correct 5 ms 9812 KB Output is correct
18 Correct 8 ms 11476 KB Output is correct
19 Correct 7 ms 11476 KB Output is correct
20 Correct 7 ms 11476 KB Output is correct
21 Correct 8 ms 11476 KB Output is correct
22 Correct 8 ms 11476 KB Output is correct
23 Correct 11 ms 11588 KB Output is correct
24 Correct 8 ms 11476 KB Output is correct
25 Correct 6 ms 9684 KB Output is correct
26 Correct 8 ms 11348 KB Output is correct
27 Correct 8 ms 11348 KB Output is correct
28 Correct 9 ms 11348 KB Output is correct
29 Correct 8 ms 11348 KB Output is correct
30 Correct 8 ms 11220 KB Output is correct
31 Correct 9 ms 11220 KB Output is correct
32 Correct 8 ms 11220 KB Output is correct
33 Correct 8 ms 11220 KB Output is correct
34 Correct 151 ms 80084 KB Output is correct
35 Correct 145 ms 84148 KB Output is correct
36 Correct 141 ms 84192 KB Output is correct
37 Correct 187 ms 85176 KB Output is correct
38 Correct 222 ms 85164 KB Output is correct
39 Correct 185 ms 85168 KB Output is correct
40 Correct 246 ms 85112 KB Output is correct
41 Correct 5 ms 9684 KB Output is correct
42 Correct 5 ms 9812 KB Output is correct
43 Correct 202 ms 68844 KB Output is correct
44 Correct 198 ms 68960 KB Output is correct
45 Correct 205 ms 68832 KB Output is correct
46 Correct 359 ms 78692 KB Output is correct
47 Correct 336 ms 77656 KB Output is correct
48 Correct 333 ms 79280 KB Output is correct
49 Correct 345 ms 77624 KB Output is correct
50 Correct 291 ms 72504 KB Output is correct
51 Correct 304 ms 72516 KB Output is correct
52 Correct 301 ms 72524 KB Output is correct
53 Correct 290 ms 72572 KB Output is correct