oj.uz

Submission #961017

# Submission time Handle Problem Language Result Execution time Memory
961017 2024-04-11T11:45:03 Z bebra Cat Exercise (JOI23_ho_t4) C++17
0 / 100
 12 ms 36948 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 = max(0, depth[v] - depth[u] - 1);
        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 = max(0, depth[u] - depth[v] - 1);
        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(n - 1);

    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);
    int64_t res = 0;
    for (int v = n - 1; 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]);
    }

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 36700 KB Output is correct
2 Correct 6 ms 36696 KB Output is correct
3 Correct 7 ms 36948 KB Output is correct
4 Correct 6 ms 36696 KB Output is correct
5 Correct 5 ms 36700 KB Output is correct
6 Correct 7 ms 36776 KB Output is correct
7 Correct 5 ms 36696 KB Output is correct
8 Incorrect 5 ms 36700 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 36700 KB Output is correct
2 Correct 6 ms 36696 KB Output is correct
3 Correct 7 ms 36948 KB Output is correct
4 Correct 6 ms 36696 KB Output is correct
5 Correct 5 ms 36700 KB Output is correct
6 Correct 7 ms 36776 KB Output is correct
7 Correct 5 ms 36696 KB Output is correct
8 Incorrect 5 ms 36700 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 36700 KB Output is correct
2 Correct 6 ms 36696 KB Output is correct
3 Correct 7 ms 36948 KB Output is correct
4 Correct 6 ms 36696 KB Output is correct
5 Correct 5 ms 36700 KB Output is correct
6 Correct 7 ms 36776 KB Output is correct
7 Correct 5 ms 36696 KB Output is correct
8 Incorrect 5 ms 36700 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 36700 KB Output is correct
2 Correct 6 ms 36696 KB Output is correct
3 Correct 7 ms 36948 KB Output is correct
4 Correct 6 ms 36696 KB Output is correct
5 Correct 5 ms 36700 KB Output is correct
6 Correct 7 ms 36776 KB Output is correct
7 Correct 5 ms 36696 KB Output is correct
8 Incorrect 5 ms 36700 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 36700 KB Output is correct
2 Correct 6 ms 36696 KB Output is correct
3 Correct 7 ms 36948 KB Output is correct
4 Correct 6 ms 36696 KB Output is correct
5 Correct 5 ms 36700 KB Output is correct
6 Correct 7 ms 36776 KB Output is correct
7 Correct 5 ms 36696 KB Output is correct
8 Incorrect 5 ms 36700 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 36708 KB Output is correct
2 Incorrect 8 ms 36700 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 36700 KB Output is correct
2 Correct 6 ms 36696 KB Output is correct
3 Correct 7 ms 36948 KB Output is correct
4 Correct 6 ms 36696 KB Output is correct
5 Correct 5 ms 36700 KB Output is correct
6 Correct 7 ms 36776 KB Output is correct
7 Correct 5 ms 36696 KB Output is correct
8 Incorrect 5 ms 36700 KB Output isn't correct
9 Halted 0 ms 0 KB -