Submission #961113

#	Time	Username	Problem	Language	Result	Execution time	Memory
961113		bebra	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	154 ms	47396 KiB

Main

#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];

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

int binup[MAX_K][MAX_N];
int depth[MAX_N];
int parent[MAX_N];

int find(int v) {
    if (parent[v] == v) {
        return v;
    } else {
        return parent[v] = find(parent[v]);
    }
}

void dfs(int v, int p) {
    parent[v] = v;
    tin[v] = timer++;
    for (auto u : g[v]) {
        if (u == p) continue;
        binup[0][u] = v;
        depth[u] = depth[v] + 1;
        dfs(u, v);
    }
    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 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, -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]];
        }
    }

    vector<int64_t> dp(n);
    for (int v = 0; v < n; ++v) {
        for (auto u : g[v]) {
            u = find(u);
            if (u < v) {
                parent[u] = v;
                dp[v] = max(dp[v], dp[u] + dist(u, v));
            }
        }
    }


    cout << dp.back() << '\n';
    
    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 23 / 23
• Subtask 7: 26 / 26