oj.uz

Submission #1042789

# Submission time Handle Problem Language Result Execution time Memory
1042789 2024-08-03T11:43:37 Z SoulKnight Cat Exercise (JOI23_ho_t4) C++17
41 / 100
 120 ms 70244 KB 
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define ln '\n'

const int N = 2e5 + 5;

const int LG = 20;
int n, glit = 1, root, p[N], mx[LG][N], up[LG][N], where[N], sz[N];
vector<int> adj[N];

int dfs(int u, int par){
    up[0][u] = par;
    mx[0][glit] = u;

    where[u] = glit;
    glit++;

    int tot = 1;
    for (auto v: adj[u]){
        if (v == par) continue;
        tot += dfs(v, u);
    }
    sz[where[u]] = tot;
    return tot;
}

int answer(int l, int r){
    if (l > r) return 0;
    int lg = log2(r-l+1);
    return p[mx[lg][l]] > p[mx[lg][r-(1<<lg)+1]]? mx[lg][l]: mx[lg][r-(1<<lg)+1];
}

bool is_ancestor(int u, int v){
    return where[u] <= where[v] && where[v] <= where[u] + sz[where[u]] - 1;
}

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

    for (int i = LG-1; i >= 0; i--){
        if (!is_ancestor(up[i][u], v)) u = up[i][u];
    }
    return up[0][u];
}

ll dist(int u, int v){
    int ances = lca(u, v);
    ll ans = 0;
    for (int i = LG-1; i >= 0; i--){
        if (!is_ancestor(up[i][u], ances)) {ans += (1 << i); u = up[i][u];}
        if (!is_ancestor(up[i][v], ances)) {ans += (1 << i); v = up[i][v];}
    }

    return ans + (u != ances) + (v != ances);
}




ll f(int l, int r, int u){
    // cout << l << ' ' << r << ' ' << u << ln;

    int nxt;
    ll ans = 0LL;

    // go to top
    nxt = answer(l, min(r, where[u]-1));
    if (nxt) ans = max(ans, dist(u, nxt) + f(l, min(r, where[u]-1), nxt));

    nxt = answer(max(l, where[u] + sz[where[u]]), r);
    if (nxt) ans = max(ans, dist(u, nxt) + f(max(l, where[u] + sz[where[u]]), r, nxt));


    // go to subtree
    for (auto v: adj[u]){
        if (v == up[0][u]) continue;
        nxt = answer(max(l, where[v]), min(r, where[v] + sz[where[v]] - 1));
        if (!nxt) continue;

        ans = max(ans, dist(u, nxt) + f(max(l, where[v]), min(r, where[v] + sz[where[v]] - 1), nxt));
    }

    return ans;
}



void solve(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 0; i < n-1; i++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    root = -1;
    for (int i = 1; i <= n; i++) if (p[i] == n) root = i;
    dfs(root, root);


    for (int i = 1; i < LG; i++){
        for (int j = 1; j <= n; j++) up[i][j] = up[i-1][up[i-1][j]];
        for (int j = 1; j + (1 << (i-1)) <= n; j++){
            mx[i][j] = (p[mx[i-1][j]] > p[mx[i-1][j + (1 << (i-1))]])? mx[i-1][j]: mx[i-1][j + (1 << (i-1))];
        }
    }

    cout << f(1, n, root) << ln;

}

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

    // int TT; cin >> TT;
    // while (TT--) {solve();}

    solve();

}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25180 KB Output is correct
2 Correct 4 ms 27308 KB Output is correct
3 Correct 3 ms 27228 KB Output is correct
4 Correct 4 ms 27228 KB Output is correct
5 Correct 3 ms 27228 KB Output is correct
6 Correct 3 ms 27228 KB Output is correct
7 Correct 3 ms 23132 KB Output is correct
8 Correct 3 ms 27228 KB Output is correct
9 Correct 3 ms 27316 KB Output is correct
10 Correct 3 ms 27228 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25180 KB Output is correct
2 Correct 4 ms 27308 KB Output is correct
3 Correct 3 ms 27228 KB Output is correct
4 Correct 4 ms 27228 KB Output is correct
5 Correct 3 ms 27228 KB Output is correct
6 Correct 3 ms 27228 KB Output is correct
7 Correct 3 ms 23132 KB Output is correct
8 Correct 3 ms 27228 KB Output is correct
9 Correct 3 ms 27316 KB Output is correct
10 Correct 3 ms 27228 KB Output is correct
11 Correct 3 ms 31324 KB Output is correct
12 Correct 3 ms 31324 KB Output is correct
13 Correct 4 ms 31412 KB Output is correct
14 Correct 3 ms 31324 KB Output is correct
15 Correct 3 ms 31324 KB Output is correct
16 Correct 4 ms 31392 KB Output is correct
17 Correct 4 ms 31324 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25180 KB Output is correct
2 Correct 4 ms 27308 KB Output is correct
3 Correct 3 ms 27228 KB Output is correct
4 Correct 4 ms 27228 KB Output is correct
5 Correct 3 ms 27228 KB Output is correct
6 Correct 3 ms 27228 KB Output is correct
7 Correct 3 ms 23132 KB Output is correct
8 Correct 3 ms 27228 KB Output is correct
9 Correct 3 ms 27316 KB Output is correct
10 Correct 3 ms 27228 KB Output is correct
11 Correct 3 ms 31324 KB Output is correct
12 Correct 3 ms 31324 KB Output is correct
13 Correct 4 ms 31412 KB Output is correct
14 Correct 3 ms 31324 KB Output is correct
15 Correct 3 ms 31324 KB Output is correct
16 Correct 4 ms 31392 KB Output is correct
17 Correct 4 ms 31324 KB Output is correct
18 Correct 5 ms 34140 KB Output is correct
19 Correct 6 ms 34224 KB Output is correct
20 Correct 5 ms 34204 KB Output is correct
21 Correct 6 ms 33884 KB Output is correct
22 Correct 5 ms 33700 KB Output is correct
23 Correct 5 ms 33772 KB Output is correct
24 Correct 5 ms 33844 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25180 KB Output is correct
2 Correct 4 ms 27308 KB Output is correct
3 Correct 3 ms 27228 KB Output is correct
4 Correct 4 ms 27228 KB Output is correct
5 Correct 3 ms 27228 KB Output is correct
6 Correct 3 ms 27228 KB Output is correct
7 Correct 3 ms 23132 KB Output is correct
8 Correct 3 ms 27228 KB Output is correct
9 Correct 3 ms 27316 KB Output is correct
10 Correct 3 ms 27228 KB Output is correct
11 Correct 3 ms 31324 KB Output is correct
12 Correct 3 ms 31324 KB Output is correct
13 Correct 4 ms 31412 KB Output is correct
14 Correct 3 ms 31324 KB Output is correct
15 Correct 3 ms 31324 KB Output is correct
16 Correct 4 ms 31392 KB Output is correct
17 Correct 4 ms 31324 KB Output is correct
18 Correct 5 ms 34140 KB Output is correct
19 Correct 6 ms 34224 KB Output is correct
20 Correct 5 ms 34204 KB Output is correct
21 Correct 6 ms 33884 KB Output is correct
22 Correct 5 ms 33700 KB Output is correct
23 Correct 5 ms 33772 KB Output is correct
24 Correct 5 ms 33844 KB Output is correct
25 Correct 3 ms 25240 KB Output is correct
26 Correct 7 ms 33892 KB Output is correct
27 Correct 7 ms 33940 KB Output is correct
28 Correct 6 ms 33884 KB Output is correct
29 Incorrect 6 ms 33896 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25180 KB Output is correct
2 Correct 4 ms 27308 KB Output is correct
3 Correct 3 ms 27228 KB Output is correct
4 Correct 4 ms 27228 KB Output is correct
5 Correct 3 ms 27228 KB Output is correct
6 Correct 3 ms 27228 KB Output is correct
7 Correct 3 ms 23132 KB Output is correct
8 Correct 3 ms 27228 KB Output is correct
9 Correct 3 ms 27316 KB Output is correct
10 Correct 3 ms 27228 KB Output is correct
11 Correct 3 ms 31324 KB Output is correct
12 Correct 3 ms 31324 KB Output is correct
13 Correct 4 ms 31412 KB Output is correct
14 Correct 3 ms 31324 KB Output is correct
15 Correct 3 ms 31324 KB Output is correct
16 Correct 4 ms 31392 KB Output is correct
17 Correct 4 ms 31324 KB Output is correct
18 Correct 5 ms 34140 KB Output is correct
19 Correct 6 ms 34224 KB Output is correct
20 Correct 5 ms 34204 KB Output is correct
21 Correct 6 ms 33884 KB Output is correct
22 Correct 5 ms 33700 KB Output is correct
23 Correct 5 ms 33772 KB Output is correct
24 Correct 5 ms 33844 KB Output is correct
25 Correct 97 ms 70244 KB Output is correct
26 Correct 120 ms 68084 KB Output is correct
27 Correct 90 ms 68256 KB Output is correct
28 Correct 74 ms 57684 KB Output is correct
29 Correct 74 ms 59472 KB Output is correct
30 Correct 80 ms 58976 KB Output is correct
31 Correct 70 ms 59476 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25180 KB Output is correct
2 Incorrect 4 ms 29276 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25180 KB Output is correct
2 Correct 4 ms 27308 KB Output is correct
3 Correct 3 ms 27228 KB Output is correct
4 Correct 4 ms 27228 KB Output is correct
5 Correct 3 ms 27228 KB Output is correct
6 Correct 3 ms 27228 KB Output is correct
7 Correct 3 ms 23132 KB Output is correct
8 Correct 3 ms 27228 KB Output is correct
9 Correct 3 ms 27316 KB Output is correct
10 Correct 3 ms 27228 KB Output is correct
11 Correct 3 ms 31324 KB Output is correct
12 Correct 3 ms 31324 KB Output is correct
13 Correct 4 ms 31412 KB Output is correct
14 Correct 3 ms 31324 KB Output is correct
15 Correct 3 ms 31324 KB Output is correct
16 Correct 4 ms 31392 KB Output is correct
17 Correct 4 ms 31324 KB Output is correct
18 Correct 5 ms 34140 KB Output is correct
19 Correct 6 ms 34224 KB Output is correct
20 Correct 5 ms 34204 KB Output is correct
21 Correct 6 ms 33884 KB Output is correct
22 Correct 5 ms 33700 KB Output is correct
23 Correct 5 ms 33772 KB Output is correct
24 Correct 5 ms 33844 KB Output is correct
25 Correct 3 ms 25240 KB Output is correct
26 Correct 7 ms 33892 KB Output is correct
27 Correct 7 ms 33940 KB Output is correct
28 Correct 6 ms 33884 KB Output is correct
29 Incorrect 6 ms 33896 KB Output isn't correct
30 Halted 0 ms 0 KB -