oj.uz

Submission #932995

# Submission time Handle Problem Language Result Execution time Memory
932995 2024-02-24T17:51:21 Z sheldon Cat Exercise (JOI23_ho_t4) C++14
100 / 100
 321 ms 64108 KB 
#include <bits/stdc++.h>

using namespace std;

const int nax = 2e5 + 5;

int height[nax], who[nax], up[nax][19], leader[nax], depth[nax];
long long dp[nax];

vector<int> edges[nax];



struct S  {
    vector<int> members;
    int mx = 0;
};

S comp[nax];


void dfs (int u, int p) {
    up[u][0] = p;
    depth[u] = depth[p] + 1;
    for (int i = 1; i < 19; ++i) {
        up[u][i] = up[up[u][i - 1]][i - 1];
    }
    for (int v : edges[u]) {
        if (v != p) {
            dfs (v, u);
        }
    }
}

int get_dist (int x, int y) {
    if (depth[x] < depth[y]) {
        swap(x, y);
    }
    int diff = depth[x] - depth[y];
    int ans = diff;
    for (int i = 0; i < 19; ++i) {
        if (diff & (1 << i)) {
            x = up[x][i];
        }
    }
    if (x == y) {
        return ans;
    }

    for (int i = 18; i >= 0; --i) {
        if (up[x][i] != up[y][i]) {
            ans += (1 << (i + 1));
            x = up[x][i];
            y = up[y][i];
        }
    }

    return ans + 2;
}

void merge (int u, int v) {
    u = leader[u];
    v = leader[v];
    if (u == v) {
        return;
    }

    if (comp[u].members.size() > comp[v].members.size()) {
        swap (u, v);
    }

    comp[v].mx = max(comp[v].mx, comp[u].mx);
    for (int x : comp[u].members) {
        leader[x] = v;
        comp[v].members.push_back(x);
    }
}

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> height[i];
        who[height[i]] = i;
        leader[i] = i;
        comp[i].members.push_back(i);
        comp[i].mx = height[i];
    }
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    dfs (1, 0);

    // cout << get_dist (2, 3) << '\n';
    for (int i = 1; i <= n; ++i) {
        int u = who[i];
        for (int v : edges[u]) {
            if (height[v] < i) {
                int me = leader[u], him = leader[v];
                dp[i] = max(dp[i], get_dist(u, who[comp[him].mx]) + dp[comp[him].mx]);
                merge (u, v);
            }
        }
    }
    cout << dp[n];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:103:21: warning: unused variable 'me' [-Wunused-variable]
  103 |                 int me = leader[u], him = leader[v];
      |                     ^~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 4 ms 15004 KB Output is correct
6 Correct 3 ms 14936 KB Output is correct
7 Correct 4 ms 14936 KB Output is correct
8 Correct 3 ms 15192 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 4 ms 15004 KB Output is correct
6 Correct 3 ms 14936 KB Output is correct
7 Correct 4 ms 14936 KB Output is correct
8 Correct 3 ms 15192 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14936 KB Output is correct
12 Correct 4 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 3 ms 14940 KB Output is correct
15 Correct 3 ms 14940 KB Output is correct
16 Correct 3 ms 14940 KB Output is correct
17 Correct 4 ms 15004 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 4 ms 15004 KB Output is correct
6 Correct 3 ms 14936 KB Output is correct
7 Correct 4 ms 14936 KB Output is correct
8 Correct 3 ms 15192 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14936 KB Output is correct
12 Correct 4 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 3 ms 14940 KB Output is correct
15 Correct 3 ms 14940 KB Output is correct
16 Correct 3 ms 14940 KB Output is correct
17 Correct 4 ms 15004 KB Output is correct
18 Correct 6 ms 15484 KB Output is correct
19 Correct 7 ms 15708 KB Output is correct
20 Correct 7 ms 15708 KB Output is correct
21 Correct 5 ms 15708 KB Output is correct
22 Correct 6 ms 15704 KB Output is correct
23 Correct 7 ms 15960 KB Output is correct
24 Correct 5 ms 15708 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 4 ms 15004 KB Output is correct
6 Correct 3 ms 14936 KB Output is correct
7 Correct 4 ms 14936 KB Output is correct
8 Correct 3 ms 15192 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14936 KB Output is correct
12 Correct 4 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 3 ms 14940 KB Output is correct
15 Correct 3 ms 14940 KB Output is correct
16 Correct 3 ms 14940 KB Output is correct
17 Correct 4 ms 15004 KB Output is correct
18 Correct 6 ms 15484 KB Output is correct
19 Correct 7 ms 15708 KB Output is correct
20 Correct 7 ms 15708 KB Output is correct
21 Correct 5 ms 15708 KB Output is correct
22 Correct 6 ms 15704 KB Output is correct
23 Correct 7 ms 15960 KB Output is correct
24 Correct 5 ms 15708 KB Output is correct
25 Correct 3 ms 14940 KB Output is correct
26 Correct 7 ms 15448 KB Output is correct
27 Correct 5 ms 15452 KB Output is correct
28 Correct 6 ms 15524 KB Output is correct
29 Correct 6 ms 15452 KB Output is correct
30 Correct 5 ms 15448 KB Output is correct
31 Correct 5 ms 15452 KB Output is correct
32 Correct 5 ms 15452 KB Output is correct
33 Correct 7 ms 15480 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 4 ms 15004 KB Output is correct
6 Correct 3 ms 14936 KB Output is correct
7 Correct 4 ms 14936 KB Output is correct
8 Correct 3 ms 15192 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14936 KB Output is correct
12 Correct 4 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 3 ms 14940 KB Output is correct
15 Correct 3 ms 14940 KB Output is correct
16 Correct 3 ms 14940 KB Output is correct
17 Correct 4 ms 15004 KB Output is correct
18 Correct 6 ms 15484 KB Output is correct
19 Correct 7 ms 15708 KB Output is correct
20 Correct 7 ms 15708 KB Output is correct
21 Correct 5 ms 15708 KB Output is correct
22 Correct 6 ms 15704 KB Output is correct
23 Correct 7 ms 15960 KB Output is correct
24 Correct 5 ms 15708 KB Output is correct
25 Correct 100 ms 57804 KB Output is correct
26 Correct 110 ms 57572 KB Output is correct
27 Correct 95 ms 57800 KB Output is correct
28 Correct 191 ms 64108 KB Output is correct
29 Correct 182 ms 63880 KB Output is correct
30 Correct 178 ms 64064 KB Output is correct
31 Correct 190 ms 64028 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 4 ms 14996 KB Output is correct
3 Correct 194 ms 49576 KB Output is correct
4 Correct 199 ms 49680 KB Output is correct
5 Correct 194 ms 49612 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14936 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 3 ms 14940 KB Output is correct
5 Correct 4 ms 15004 KB Output is correct
6 Correct 3 ms 14936 KB Output is correct
7 Correct 4 ms 14936 KB Output is correct
8 Correct 3 ms 15192 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 3 ms 14940 KB Output is correct
11 Correct 3 ms 14936 KB Output is correct
12 Correct 4 ms 14940 KB Output is correct
13 Correct 3 ms 14940 KB Output is correct
14 Correct 3 ms 14940 KB Output is correct
15 Correct 3 ms 14940 KB Output is correct
16 Correct 3 ms 14940 KB Output is correct
17 Correct 4 ms 15004 KB Output is correct
18 Correct 6 ms 15484 KB Output is correct
19 Correct 7 ms 15708 KB Output is correct
20 Correct 7 ms 15708 KB Output is correct
21 Correct 5 ms 15708 KB Output is correct
22 Correct 6 ms 15704 KB Output is correct
23 Correct 7 ms 15960 KB Output is correct
24 Correct 5 ms 15708 KB Output is correct
25 Correct 3 ms 14940 KB Output is correct
26 Correct 7 ms 15448 KB Output is correct
27 Correct 5 ms 15452 KB Output is correct
28 Correct 6 ms 15524 KB Output is correct
29 Correct 6 ms 15452 KB Output is correct
30 Correct 5 ms 15448 KB Output is correct
31 Correct 5 ms 15452 KB Output is correct
32 Correct 5 ms 15452 KB Output is correct
33 Correct 7 ms 15480 KB Output is correct
34 Correct 100 ms 57804 KB Output is correct
35 Correct 110 ms 57572 KB Output is correct
36 Correct 95 ms 57800 KB Output is correct
37 Correct 191 ms 64108 KB Output is correct
38 Correct 182 ms 63880 KB Output is correct
39 Correct 178 ms 64064 KB Output is correct
40 Correct 190 ms 64028 KB Output is correct
41 Correct 3 ms 14940 KB Output is correct
42 Correct 4 ms 14996 KB Output is correct
43 Correct 194 ms 49576 KB Output is correct
44 Correct 199 ms 49680 KB Output is correct
45 Correct 194 ms 49612 KB Output is correct
46 Correct 280 ms 53712 KB Output is correct
47 Correct 289 ms 52888 KB Output is correct
48 Correct 259 ms 54060 KB Output is correct
49 Correct 261 ms 52684 KB Output is correct
50 Correct 270 ms 51396 KB Output is correct
51 Correct 258 ms 50988 KB Output is correct
52 Correct 321 ms 51456 KB Output is correct
53 Correct 261 ms 51076 KB Output is correct