oj.uz

Submission #961039

# Submission time Handle Problem Language Result Execution time Memory
961039 2024-04-11T12:30:32 Z bebra Cat Exercise (JOI23_ho_t4) C++17
21 / 100
 2000 ms 55380 KB 
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;




const int MAX_N = 2e5 + 5;
const int MAX_K = 20;
vector<int> g[MAX_N];
bool used[MAX_N];

int tin[MAX_N];
int tout[MAX_N];
int timer = 0;

int binup[MAX_K][MAX_N];
int max_vertex[MAX_K][MAX_N];

int depth[MAX_N];

void dfs(int v) {
    tin[v] = timer++;
    for (auto u : g[v]) {
        g[u].erase(find(g[u].begin(), g[u].end(), v));

        binup[0][u] = v;
        max_vertex[0][v] = v;
        depth[u] = depth[v] + 1;
        dfs(u);
    }
    tout[v] = timer++;
}

bool is_parent(int p, int v) {
    return (tin[p] <= tin[v] && tout[v] <= tout[p]);
}

int lca(int u, int v) {
    if (is_parent(u, v)) return u;
    if (is_parent(v, u)) return v;

    for (int k = MAX_K - 1; k >= 0; --k) {
        if (!is_parent(binup[k][v], u)) {
            v = binup[k][v];
        }
    }
    return binup[0][v];
}

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

int max_v(int u, int v) {
    if (is_parent(u, v)) {
        v = binup[0][v];
        int w = depth[v] - depth[u];
        int res = -1;
        for (int k = MAX_K - 1; k >= 0; --k) {
            if (w & (1 << k)) {
                res = max(res, max_vertex[k][v]);
                v = binup[k][v];
            }
        }
        return res;
    } else if (is_parent(v, u)) {
        u = binup[0][u];
        int w = depth[u] - depth[v];
        int res = -1;
        for (int k = MAX_K - 1; k >= 0; --k) {
            if (w & (1 << k)) {
                res = max(res, max_vertex[k][u]);
                u = binup[k][u];
            }
        }
        return res;
    } else {
        v = binup[0][v];
        u = binup[0][u];

        int c = lca(u, v);
        int w1 = depth[u] - depth[c];
        int res1 = -1;
        for (int k = MAX_K - 1; k >= 0; --k) {
            if (w1 & (1 << k)) {
                res1 = max(res1, max_vertex[k][u]);
                u = binup[k][u];
            }
        }
        int w2 = depth[v] - depth[c];
        int res2 = -1;
        for (int k = MAX_K - 1; k >= 0; --k) {
            if (w2 & (1 << k)) {
                res2 = max(res2, max_vertex[k][v]);
                v = binup[k][v];
            }
        }
        return max(c, max(res1, res2));
    }
}

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

    int n;
    cin >> n;
    vector<int> p(n);
    for (auto& x : p) {
        cin >> x;
        --x;
    }

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;

        u = p[u];
        v = p[v];

        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(0);

    for (int k = 1; k < MAX_K; ++k) {
        for (int v = 0; v < n; ++v) {
            binup[k][v] = binup[k - 1][binup[k - 1][v]];
            max_vertex[k][v] = max(max_vertex[k - 1][v], max_vertex[k - 1][binup[k - 1][v]]);
        }
    }

    vector<int64_t> dp(n, -1e9);
    dp.back() = 0;
    int64_t res = 0;
    for (int v = n - 2; v >= 0; --v) {
        for (int u = v + 1; u < n; ++u) {
            // dbg(u);
            // dbg(v);
            // dbg(max_v(u, v));
            if (max_v(u, v) < min(u, v)) {
                dp[v] = max(dp[v], dp[u] + dist(u, v));
            }
        }
        res = max(res, dp[v]);
        // cerr << endl;
        // dbg(v);
        // dbg(dp[v]);
        // cerr << endl;
    }

    // dbg(max_v(2, 0));

    cout << res << '\n';
    
    return 0;
}


/*
16
16 8 7 9 1 5 3 13 11 15 12 10 2 4 14 6
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16

22

*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 36696 KB Output is correct
2 Correct 5 ms 36700 KB Output is correct
3 Correct 5 ms 36700 KB Output is correct
4 Correct 6 ms 36696 KB Output is correct
5 Correct 5 ms 36696 KB Output is correct
6 Correct 5 ms 36700 KB Output is correct
7 Correct 5 ms 36756 KB Output is correct
8 Correct 5 ms 36700 KB Output is correct
9 Correct 6 ms 36776 KB Output is correct
10 Correct 5 ms 36700 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 36696 KB Output is correct
2 Correct 5 ms 36700 KB Output is correct
3 Correct 5 ms 36700 KB Output is correct
4 Correct 6 ms 36696 KB Output is correct
5 Correct 5 ms 36696 KB Output is correct
6 Correct 5 ms 36700 KB Output is correct
7 Correct 5 ms 36756 KB Output is correct
8 Correct 5 ms 36700 KB Output is correct
9 Correct 6 ms 36776 KB Output is correct
10 Correct 5 ms 36700 KB Output is correct
11 Correct 11 ms 36700 KB Output is correct
12 Correct 11 ms 36824 KB Output is correct
13 Correct 8 ms 36700 KB Output is correct
14 Correct 10 ms 36700 KB Output is correct
15 Correct 11 ms 36700 KB Output is correct
16 Correct 12 ms 36788 KB Output is correct
17 Correct 9 ms 36700 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 36696 KB Output is correct
2 Correct 5 ms 36700 KB Output is correct
3 Correct 5 ms 36700 KB Output is correct
4 Correct 6 ms 36696 KB Output is correct
5 Correct 5 ms 36696 KB Output is correct
6 Correct 5 ms 36700 KB Output is correct
7 Correct 5 ms 36756 KB Output is correct
8 Correct 5 ms 36700 KB Output is correct
9 Correct 6 ms 36776 KB Output is correct
10 Correct 5 ms 36700 KB Output is correct
11 Correct 11 ms 36700 KB Output is correct
12 Correct 11 ms 36824 KB Output is correct
13 Correct 8 ms 36700 KB Output is correct
14 Correct 10 ms 36700 KB Output is correct
15 Correct 11 ms 36700 KB Output is correct
16 Correct 12 ms 36788 KB Output is correct
17 Correct 9 ms 36700 KB Output is correct
18 Correct 1386 ms 37256 KB Output is correct
19 Correct 690 ms 37464 KB Output is correct
20 Correct 722 ms 37468 KB Output is correct
21 Correct 1668 ms 37288 KB Output is correct
22 Correct 1039 ms 37432 KB Output is correct
23 Correct 1640 ms 37320 KB Output is correct
24 Correct 1134 ms 37212 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 36696 KB Output is correct
2 Correct 5 ms 36700 KB Output is correct
3 Correct 5 ms 36700 KB Output is correct
4 Correct 6 ms 36696 KB Output is correct
5 Correct 5 ms 36696 KB Output is correct
6 Correct 5 ms 36700 KB Output is correct
7 Correct 5 ms 36756 KB Output is correct
8 Correct 5 ms 36700 KB Output is correct
9 Correct 6 ms 36776 KB Output is correct
10 Correct 5 ms 36700 KB Output is correct
11 Correct 11 ms 36700 KB Output is correct
12 Correct 11 ms 36824 KB Output is correct
13 Correct 8 ms 36700 KB Output is correct
14 Correct 10 ms 36700 KB Output is correct
15 Correct 11 ms 36700 KB Output is correct
16 Correct 12 ms 36788 KB Output is correct
17 Correct 9 ms 36700 KB Output is correct
18 Correct 1386 ms 37256 KB Output is correct
19 Correct 690 ms 37464 KB Output is correct
20 Correct 722 ms 37468 KB Output is correct
21 Correct 1668 ms 37288 KB Output is correct
22 Correct 1039 ms 37432 KB Output is correct
23 Correct 1640 ms 37320 KB Output is correct
24 Correct 1134 ms 37212 KB Output is correct
25 Correct 5 ms 36700 KB Output is correct
26 Correct 1058 ms 37340 KB Output is correct
27 Correct 1055 ms 37336 KB Output is correct
28 Correct 1062 ms 37332 KB Output is correct
29 Correct 1080 ms 37332 KB Output is correct
30 Execution timed out 2005 ms 37068 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 36696 KB Output is correct
2 Correct 5 ms 36700 KB Output is correct
3 Correct 5 ms 36700 KB Output is correct
4 Correct 6 ms 36696 KB Output is correct
5 Correct 5 ms 36696 KB Output is correct
6 Correct 5 ms 36700 KB Output is correct
7 Correct 5 ms 36756 KB Output is correct
8 Correct 5 ms 36700 KB Output is correct
9 Correct 6 ms 36776 KB Output is correct
10 Correct 5 ms 36700 KB Output is correct
11 Correct 11 ms 36700 KB Output is correct
12 Correct 11 ms 36824 KB Output is correct
13 Correct 8 ms 36700 KB Output is correct
14 Correct 10 ms 36700 KB Output is correct
15 Correct 11 ms 36700 KB Output is correct
16 Correct 12 ms 36788 KB Output is correct
17 Correct 9 ms 36700 KB Output is correct
18 Correct 1386 ms 37256 KB Output is correct
19 Correct 690 ms 37464 KB Output is correct
20 Correct 722 ms 37468 KB Output is correct
21 Correct 1668 ms 37288 KB Output is correct
22 Correct 1039 ms 37432 KB Output is correct
23 Correct 1640 ms 37320 KB Output is correct
24 Correct 1134 ms 37212 KB Output is correct
25 Execution timed out 2063 ms 55380 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 36700 KB Output is correct
2 Correct 10 ms 36700 KB Output is correct
3 Execution timed out 2041 ms 47432 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 36696 KB Output is correct
2 Correct 5 ms 36700 KB Output is correct
3 Correct 5 ms 36700 KB Output is correct
4 Correct 6 ms 36696 KB Output is correct
5 Correct 5 ms 36696 KB Output is correct
6 Correct 5 ms 36700 KB Output is correct
7 Correct 5 ms 36756 KB Output is correct
8 Correct 5 ms 36700 KB Output is correct
9 Correct 6 ms 36776 KB Output is correct
10 Correct 5 ms 36700 KB Output is correct
11 Correct 11 ms 36700 KB Output is correct
12 Correct 11 ms 36824 KB Output is correct
13 Correct 8 ms 36700 KB Output is correct
14 Correct 10 ms 36700 KB Output is correct
15 Correct 11 ms 36700 KB Output is correct
16 Correct 12 ms 36788 KB Output is correct
17 Correct 9 ms 36700 KB Output is correct
18 Correct 1386 ms 37256 KB Output is correct
19 Correct 690 ms 37464 KB Output is correct
20 Correct 722 ms 37468 KB Output is correct
21 Correct 1668 ms 37288 KB Output is correct
22 Correct 1039 ms 37432 KB Output is correct
23 Correct 1640 ms 37320 KB Output is correct
24 Correct 1134 ms 37212 KB Output is correct
25 Correct 5 ms 36700 KB Output is correct
26 Correct 1058 ms 37340 KB Output is correct
27 Correct 1055 ms 37336 KB Output is correct
28 Correct 1062 ms 37332 KB Output is correct
29 Correct 1080 ms 37332 KB Output is correct
30 Execution timed out 2005 ms 37068 KB Time limit exceeded
31 Halted 0 ms 0 KB -