oj.uz

Submission #1107433

# Submission time Handle Problem Language Result Execution time Memory
1107433 2024-11-01T08:36:38 Z Zero_OP Cat Exercise (JOI23_ho_t4) C++14
54 / 100
 105 ms 49576 KB 
#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<int> 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.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 3 ms 1432 KB Output is correct
19 Correct 3 ms 1360 KB Output is correct
20 Correct 3 ms 1532 KB Output is correct
21 Correct 3 ms 1360 KB Output is correct
22 Correct 3 ms 1532 KB Output is correct
23 Correct 2 ms 1360 KB Output is correct
24 Correct 3 ms 1360 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 3 ms 1432 KB Output is correct
19 Correct 3 ms 1360 KB Output is correct
20 Correct 3 ms 1532 KB Output is correct
21 Correct 3 ms 1360 KB Output is correct
22 Correct 3 ms 1532 KB Output is correct
23 Correct 2 ms 1360 KB Output is correct
24 Correct 3 ms 1360 KB Output is correct
25 Correct 1 ms 508 KB Output is correct
26 Correct 3 ms 1360 KB Output is correct
27 Correct 3 ms 1360 KB Output is correct
28 Correct 3 ms 1372 KB Output is correct
29 Correct 3 ms 1360 KB Output is correct
30 Correct 3 ms 1104 KB Output is correct
31 Correct 3 ms 1104 KB Output is correct
32 Correct 3 ms 1104 KB Output is correct
33 Correct 3 ms 1104 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 3 ms 1432 KB Output is correct
19 Correct 3 ms 1360 KB Output is correct
20 Correct 3 ms 1532 KB Output is correct
21 Correct 3 ms 1360 KB Output is correct
22 Correct 3 ms 1532 KB Output is correct
23 Correct 2 ms 1360 KB Output is correct
24 Correct 3 ms 1360 KB Output is correct
25 Incorrect 105 ms 49576 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 336 KB Output is correct
2 Correct 1 ms 504 KB Output is correct
3 Correct 95 ms 30936 KB Output is correct
4 Correct 104 ms 31000 KB Output is correct
5 Correct 101 ms 30840 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 3 ms 1432 KB Output is correct
19 Correct 3 ms 1360 KB Output is correct
20 Correct 3 ms 1532 KB Output is correct
21 Correct 3 ms 1360 KB Output is correct
22 Correct 3 ms 1532 KB Output is correct
23 Correct 2 ms 1360 KB Output is correct
24 Correct 3 ms 1360 KB Output is correct
25 Correct 1 ms 508 KB Output is correct
26 Correct 3 ms 1360 KB Output is correct
27 Correct 3 ms 1360 KB Output is correct
28 Correct 3 ms 1372 KB Output is correct
29 Correct 3 ms 1360 KB Output is correct
30 Correct 3 ms 1104 KB Output is correct
31 Correct 3 ms 1104 KB Output is correct
32 Correct 3 ms 1104 KB Output is correct
33 Correct 3 ms 1104 KB Output is correct
34 Incorrect 105 ms 49576 KB Output isn't correct
35 Halted 0 ms 0 KB -