oj.uz

Submission #922652

# Submission time Handle Problem Language Result Execution time Memory
922652 2024-02-05T21:43:15 Z ksujay2 Cat Exercise (JOI23_ho_t4) C++17
54 / 100
 311 ms 58236 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N; cin >> N;
    vector<int> P(N + 1), revP(N + 1);
    for(int i = 1; i <= N; i++) cin >> P[i], revP[P[i]] = i;
    vector<vector<int>> adj(N + 1);
    for(int i = 0; i < N - 1; i++) {
        int A, B; cin >> A >> B;
        adj[A].push_back(B);
        adj[B].push_back(A);
    }
    vector<vector<int>> jmp(N + 1, vector<int>(19));
    vector<int> dep(N + 1);
    function<void(int, int)> dfs = [&] (int s, int e) {
        jmp[s][0] = e;
        dep[s] = dep[e] + 1;
        for(int i = 0; i < 18; i++) {
            jmp[s][i + 1] = jmp[jmp[s][i]][i];
        }
        for(int u : adj[s]) if(u != e) dfs(u, s);
    };
    dfs(1, 0);
    auto lca = [&] (int a, int b) {
        if(dep[a] < dep[b]) swap(a, b);
        for(int i = 18; i >= 0; i--) {
            if(dep[jmp[a][i]] >= dep[b])
                a = jmp[a][i];
        }
        if(a == b) return a;
        for(int i = 18; i >= 0; i--) {
            if(jmp[a][i] != jmp[b][i]) {
                a = jmp[a][i];
                b = jmp[b][i];
            }
        }
        return jmp[a][0];
    };
    auto dist = [&] (int s, int t) {
        return dep[s] + dep[t] - 2 * dep[lca(s, t)];
    };
    vector<int> e(N + 1, -1);
    function<int(int)> get = [&] (int s) {
        return e[s] < 0 ? s : (e[s] = get(e[s]));
    };
    vector<int> dp(N + 1);
    for(int i = 1; i <= N; i++) {
        int s = revP[i];
        for(int u : adj[s]) {
            if(P[u] <= i) {
                dp[s] = max(dp[s], dist(s, get(u)) + dp[get(u)]);
                e[s] += e[get(u)];
                e[get(u)] = s;
            }
        }
    }
    cout << dp[revP[N]] << endl;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 5 ms 1624 KB Output is correct
19 Correct 5 ms 1628 KB Output is correct
20 Correct 6 ms 1628 KB Output is correct
21 Correct 6 ms 1624 KB Output is correct
22 Correct 5 ms 1628 KB Output is correct
23 Correct 7 ms 1628 KB Output is correct
24 Correct 5 ms 1628 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 5 ms 1624 KB Output is correct
19 Correct 5 ms 1628 KB Output is correct
20 Correct 6 ms 1628 KB Output is correct
21 Correct 6 ms 1624 KB Output is correct
22 Correct 5 ms 1628 KB Output is correct
23 Correct 7 ms 1628 KB Output is correct
24 Correct 5 ms 1628 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 6 ms 1628 KB Output is correct
27 Correct 8 ms 1624 KB Output is correct
28 Correct 6 ms 1624 KB Output is correct
29 Correct 6 ms 1628 KB Output is correct
30 Correct 6 ms 1312 KB Output is correct
31 Correct 5 ms 1372 KB Output is correct
32 Correct 6 ms 1372 KB Output is correct
33 Correct 5 ms 1372 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 5 ms 1624 KB Output is correct
19 Correct 5 ms 1628 KB Output is correct
20 Correct 6 ms 1628 KB Output is correct
21 Correct 6 ms 1624 KB Output is correct
22 Correct 5 ms 1628 KB Output is correct
23 Correct 7 ms 1628 KB Output is correct
24 Correct 5 ms 1628 KB Output is correct
25 Incorrect 228 ms 58236 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 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 311 ms 42564 KB Output is correct
4 Correct 292 ms 42320 KB Output is correct
5 Correct 299 ms 42312 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 5 ms 1624 KB Output is correct
19 Correct 5 ms 1628 KB Output is correct
20 Correct 6 ms 1628 KB Output is correct
21 Correct 6 ms 1624 KB Output is correct
22 Correct 5 ms 1628 KB Output is correct
23 Correct 7 ms 1628 KB Output is correct
24 Correct 5 ms 1628 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 6 ms 1628 KB Output is correct
27 Correct 8 ms 1624 KB Output is correct
28 Correct 6 ms 1624 KB Output is correct
29 Correct 6 ms 1628 KB Output is correct
30 Correct 6 ms 1312 KB Output is correct
31 Correct 5 ms 1372 KB Output is correct
32 Correct 6 ms 1372 KB Output is correct
33 Correct 5 ms 1372 KB Output is correct
34 Incorrect 228 ms 58236 KB Output isn't correct
35 Halted 0 ms 0 KB -