Submission #1107435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107435		Zero_OP	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	170 ms	54468 KiB

Main

#include <bits/stdc++.h>

using namespace std;

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b){
            return a = b, true;
        } return false;
    }

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

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    struct DisjointSet{
        vector<int> lab, mx;
        DisjointSet(int n) : lab(n, -1), mx(n) {
            for(int i = 0; i < n; ++i) mx[i] = i;
        }

        int root(int u){
            return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
        }

        bool unite(int u, int v){
            u = root(u);
            v = root(v);
            if(u == v) return false;
            if(lab[u] > lab[v]) swap(u, v);
            lab[u] += lab[v];
            lab[v] = u;
            maximize(mx[u], mx[v]);
            return true;
        }

        int maxLabel(int u){
            return mx[root(u)];
        }
    };

    int N;
    cin >> N;
    vector<int> P(N);
    for(int i = 0; i < N; ++i) cin >> P[i], --P[i];

    vector<vector<int>> adj(N);
    for(int i = 1; i < N; ++i){
        int u, v;
        cin >> u >> v;
        --u, --v;
        u = P[u];
        v = P[v];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int timerdfs = 0;
    vector<int> depth(N);
    vector<int> tin(N), tout(N);
    vector<vector<int>> lift(32 - __builtin_clz(N), vector<int>(N));

    function<void(int, int)> dfs = [&](int u, int pre){
        tin[u] = ++timerdfs;
        for(int v : adj[u]) if(v != pre){
            depth[v] = depth[u] + 1;
            lift[0][v] = u;
            for(int i = 1; (1 << i) <= depth[v]; ++i)
                lift[i][v] = lift[i - 1][lift[i - 1][v]];
            dfs(v, u);
        }
        tout[u] = timerdfs;
    };

    auto inside = [&](int u, int v) -> bool{
        return tin[u] <= tin[v] && tout[v] <= tout[u];
    };

    auto getLCA = [&](int u, int v) -> int{
        if(inside(u, v)) return u;
        if(inside(v, u)) return v;
        for(int i = 31 - __builtin_clz(depth[u]); i >= 0; --i){
            if(depth[u] >= (1 << i) && !inside(lift[i][u], v)){
                u = lift[i][u];
            }
        }
        return lift[0][u];
    };

    auto distance = [&](int u, int v) -> int{
        return depth[u] + depth[v] - 2 * depth[getLCA(u, v)];
    };


    dfs(N - 1, -1);
    DisjointSet dsu(N);

    vector<long long> dp(N, 0);

    for(int i = 1; i < N; ++i){
        for(int j : adj[i]) if(j < i){
            int mx = dsu.maxLabel(j);
            maximize(dp[i], dp[mx] + distance(mx, i));
            dsu.unite(i, j);
        }
    }

    cout << dp[N - 1] << '\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