oj.uz

Submission #1038457

# Submission time Handle Problem Language Result Execution time Memory
1038457 2024-07-29T20:03:35 Z SoulKnight Cat Exercise (JOI23_ho_t4) C++17
21 / 100
 91 ms 67156 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, p[N], mx[LG][N], up[LG][N], where[N], sz[N];
vector<int> adj[N];
bool used[N];

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

    where[u] = 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];
}

int dist(int u, int v){
    int ances = lca(u, v);
    int 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);
}

int f(int u, int tp, int btm){
    used[u] = 1;

    // cout << u << ' ' << tp << ' ' << btm << ln;

    int res = 0;
    for (auto v: adj[u]){
        if (v == up[0][u]) continue;
        if (used[v]) continue;
        // cout << "checking " << v << ln;

        int nxt;
        if (btm == -1) nxt = answer(where[v],
                                    where[v] + sz[where[v]] - 1);

        else nxt = max(answer(where[v], where[btm]-1),
                       answer(where[btm] + sz[where[btm]], where[v] + sz[where[v]]-1),
                       [&](int x, int y){return p[x] < p[y];});
        // cout << "into " << nxt << ln;
        if (!used[nxt] && nxt) res = max(res, dist(u, nxt) + f(nxt, v, btm));
    }

    int par = up[0][u];
    if (par == u) return res;

    int nxt;
    nxt = max(answer(where[tp], where[u] - 1),
              answer(where[u] + sz[where[u]], where[tp] + sz[where[tp]] - 1),
              [&](int x, int y){return p[x] < p[y];});
    if (!used[nxt] && nxt) res = max(res, dist(u, nxt) + f(nxt, tp, u));

    used[u] = 0;
    return res;
}


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);
    }
    int root = -1;
    for (int i = 1; i <= n; i++) if (p[i] == n) root = i;
    dfs(root, root);


    // for (int i = 1; i <= n; i++) cout << where[i] << " ";
    // cout << ln;
    // for (int i = 1; i <= n; i++) cout << sz[where[i]] << " ";

    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(root, root, -1) << ln;
    // cout << where[1] << ' ' << where[1] + sz[where[1]] - 1 << ln;
    // cout << answer(where[1], where[1] + sz[1] -1) << ln;
    // for (int i = 1; i <= n; i++) cout << mx[0][i] << ' ';

}

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

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

    solve();

}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24920 KB Output is correct
2 Correct 3 ms 26968 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 27104 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 3 ms 26972 KB Output is correct
7 Correct 2 ms 24924 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 3 ms 26972 KB Output is correct
10 Correct 3 ms 27104 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24920 KB Output is correct
2 Correct 3 ms 26968 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 27104 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 3 ms 26972 KB Output is correct
7 Correct 2 ms 24924 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 3 ms 26972 KB Output is correct
10 Correct 3 ms 27104 KB Output is correct
11 Correct 3 ms 31068 KB Output is correct
12 Correct 3 ms 31068 KB Output is correct
13 Correct 4 ms 31068 KB Output is correct
14 Correct 4 ms 31068 KB Output is correct
15 Correct 3 ms 31068 KB Output is correct
16 Correct 3 ms 31068 KB Output is correct
17 Correct 3 ms 31068 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24920 KB Output is correct
2 Correct 3 ms 26968 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 27104 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 3 ms 26972 KB Output is correct
7 Correct 2 ms 24924 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 3 ms 26972 KB Output is correct
10 Correct 3 ms 27104 KB Output is correct
11 Correct 3 ms 31068 KB Output is correct
12 Correct 3 ms 31068 KB Output is correct
13 Correct 4 ms 31068 KB Output is correct
14 Correct 4 ms 31068 KB Output is correct
15 Correct 3 ms 31068 KB Output is correct
16 Correct 3 ms 31068 KB Output is correct
17 Correct 3 ms 31068 KB Output is correct
18 Correct 5 ms 33884 KB Output is correct
19 Correct 8 ms 33924 KB Output is correct
20 Correct 5 ms 33844 KB Output is correct
21 Correct 5 ms 33624 KB Output is correct
22 Correct 5 ms 33628 KB Output is correct
23 Correct 5 ms 33588 KB Output is correct
24 Correct 8 ms 33628 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24920 KB Output is correct
2 Correct 3 ms 26968 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 27104 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 3 ms 26972 KB Output is correct
7 Correct 2 ms 24924 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 3 ms 26972 KB Output is correct
10 Correct 3 ms 27104 KB Output is correct
11 Correct 3 ms 31068 KB Output is correct
12 Correct 3 ms 31068 KB Output is correct
13 Correct 4 ms 31068 KB Output is correct
14 Correct 4 ms 31068 KB Output is correct
15 Correct 3 ms 31068 KB Output is correct
16 Correct 3 ms 31068 KB Output is correct
17 Correct 3 ms 31068 KB Output is correct
18 Correct 5 ms 33884 KB Output is correct
19 Correct 8 ms 33924 KB Output is correct
20 Correct 5 ms 33844 KB Output is correct
21 Correct 5 ms 33624 KB Output is correct
22 Correct 5 ms 33628 KB Output is correct
23 Correct 5 ms 33588 KB Output is correct
24 Correct 8 ms 33628 KB Output is correct
25 Correct 3 ms 24924 KB Output is correct
26 Correct 6 ms 33884 KB Output is correct
27 Correct 6 ms 33756 KB Output is correct
28 Correct 6 ms 33628 KB Output is correct
29 Incorrect 6 ms 33780 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24920 KB Output is correct
2 Correct 3 ms 26968 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 27104 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 3 ms 26972 KB Output is correct
7 Correct 2 ms 24924 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 3 ms 26972 KB Output is correct
10 Correct 3 ms 27104 KB Output is correct
11 Correct 3 ms 31068 KB Output is correct
12 Correct 3 ms 31068 KB Output is correct
13 Correct 4 ms 31068 KB Output is correct
14 Correct 4 ms 31068 KB Output is correct
15 Correct 3 ms 31068 KB Output is correct
16 Correct 3 ms 31068 KB Output is correct
17 Correct 3 ms 31068 KB Output is correct
18 Correct 5 ms 33884 KB Output is correct
19 Correct 8 ms 33924 KB Output is correct
20 Correct 5 ms 33844 KB Output is correct
21 Correct 5 ms 33624 KB Output is correct
22 Correct 5 ms 33628 KB Output is correct
23 Correct 5 ms 33588 KB Output is correct
24 Correct 8 ms 33628 KB Output is correct
25 Incorrect 91 ms 67156 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

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

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24920 KB Output is correct
2 Correct 3 ms 26968 KB Output is correct
3 Correct 3 ms 26972 KB Output is correct
4 Correct 3 ms 27104 KB Output is correct
5 Correct 3 ms 26972 KB Output is correct
6 Correct 3 ms 26972 KB Output is correct
7 Correct 2 ms 24924 KB Output is correct
8 Correct 3 ms 26972 KB Output is correct
9 Correct 3 ms 26972 KB Output is correct
10 Correct 3 ms 27104 KB Output is correct
11 Correct 3 ms 31068 KB Output is correct
12 Correct 3 ms 31068 KB Output is correct
13 Correct 4 ms 31068 KB Output is correct
14 Correct 4 ms 31068 KB Output is correct
15 Correct 3 ms 31068 KB Output is correct
16 Correct 3 ms 31068 KB Output is correct
17 Correct 3 ms 31068 KB Output is correct
18 Correct 5 ms 33884 KB Output is correct
19 Correct 8 ms 33924 KB Output is correct
20 Correct 5 ms 33844 KB Output is correct
21 Correct 5 ms 33624 KB Output is correct
22 Correct 5 ms 33628 KB Output is correct
23 Correct 5 ms 33588 KB Output is correct
24 Correct 8 ms 33628 KB Output is correct
25 Correct 3 ms 24924 KB Output is correct
26 Correct 6 ms 33884 KB Output is correct
27 Correct 6 ms 33756 KB Output is correct
28 Correct 6 ms 33628 KB Output is correct
29 Incorrect 6 ms 33780 KB Output isn't correct
30 Halted 0 ms 0 KB -