oj.uz

Submission #1038466

# Submission time Handle Problem Language Result Execution time Memory
1038466 2024-07-29T20:17:46 Z SoulKnight Cat Exercise (JOI23_ho_t4) C++17
41 / 100
 1020 ms 1048576 KB 
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define ln '\n'

const ll N = 2e5 + 5;
const ll LG = 20;
ll n, glit = 1, p[N], mx[LG][N], up[LG][N], where[N], sz[N];
vector<ll> adj[N];

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

    where[u] = glit++;

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

ll answer(ll l, ll r){
    if (l > r) return 0;
    ll 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(ll u, ll v){
    return where[u] <= where[v] && where[v] <= where[u] + sz[where[u]] - 1;
}

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

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

ll dist(ll u, ll v){
    ll ances = lca(u, v);
    ll ans = 0;
    for (ll 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(ll u, ll tp, ll btm){
    ll res = 0, nxt;
    for (auto v: adj[u]){
        if (v == up[0][u]) continue;


        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),
                       [&](ll x, ll y){return p[x] < p[y];});

        if (nxt) res = max(res, dist(u, nxt) + f(nxt, v, btm));
    }


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


    return res;
}


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


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

    for (ll i = 1; i < LG; i++){
        for (ll j = 1; j <= n; j++) up[i][j] = up[i-1][up[i-1][j]];
        for (ll 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 (ll 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 4 ms 45656 KB Output is correct
2 Correct 5 ms 49756 KB Output is correct
3 Correct 5 ms 49752 KB Output is correct
4 Correct 5 ms 49848 KB Output is correct
5 Correct 5 ms 49756 KB Output is correct
6 Correct 5 ms 49756 KB Output is correct
7 Correct 4 ms 43612 KB Output is correct
8 Correct 5 ms 49756 KB Output is correct
9 Correct 5 ms 49752 KB Output is correct
10 Correct 5 ms 49756 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 45656 KB Output is correct
2 Correct 5 ms 49756 KB Output is correct
3 Correct 5 ms 49752 KB Output is correct
4 Correct 5 ms 49848 KB Output is correct
5 Correct 5 ms 49756 KB Output is correct
6 Correct 5 ms 49756 KB Output is correct
7 Correct 4 ms 43612 KB Output is correct
8 Correct 5 ms 49756 KB Output is correct
9 Correct 5 ms 49752 KB Output is correct
10 Correct 5 ms 49756 KB Output is correct
11 Correct 5 ms 55900 KB Output is correct
12 Correct 5 ms 55900 KB Output is correct
13 Correct 5 ms 55900 KB Output is correct
14 Correct 5 ms 55900 KB Output is correct
15 Correct 6 ms 55900 KB Output is correct
16 Correct 6 ms 55900 KB Output is correct
17 Correct 6 ms 55900 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 45656 KB Output is correct
2 Correct 5 ms 49756 KB Output is correct
3 Correct 5 ms 49752 KB Output is correct
4 Correct 5 ms 49848 KB Output is correct
5 Correct 5 ms 49756 KB Output is correct
6 Correct 5 ms 49756 KB Output is correct
7 Correct 4 ms 43612 KB Output is correct
8 Correct 5 ms 49756 KB Output is correct
9 Correct 5 ms 49752 KB Output is correct
10 Correct 5 ms 49756 KB Output is correct
11 Correct 5 ms 55900 KB Output is correct
12 Correct 5 ms 55900 KB Output is correct
13 Correct 5 ms 55900 KB Output is correct
14 Correct 5 ms 55900 KB Output is correct
15 Correct 6 ms 55900 KB Output is correct
16 Correct 6 ms 55900 KB Output is correct
17 Correct 6 ms 55900 KB Output is correct
18 Correct 8 ms 62876 KB Output is correct
19 Correct 8 ms 62812 KB Output is correct
20 Correct 8 ms 62848 KB Output is correct
21 Correct 10 ms 62556 KB Output is correct
22 Correct 9 ms 62300 KB Output is correct
23 Correct 8 ms 62296 KB Output is correct
24 Correct 7 ms 62504 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 45656 KB Output is correct
2 Correct 5 ms 49756 KB Output is correct
3 Correct 5 ms 49752 KB Output is correct
4 Correct 5 ms 49848 KB Output is correct
5 Correct 5 ms 49756 KB Output is correct
6 Correct 5 ms 49756 KB Output is correct
7 Correct 4 ms 43612 KB Output is correct
8 Correct 5 ms 49756 KB Output is correct
9 Correct 5 ms 49752 KB Output is correct
10 Correct 5 ms 49756 KB Output is correct
11 Correct 5 ms 55900 KB Output is correct
12 Correct 5 ms 55900 KB Output is correct
13 Correct 5 ms 55900 KB Output is correct
14 Correct 5 ms 55900 KB Output is correct
15 Correct 6 ms 55900 KB Output is correct
16 Correct 6 ms 55900 KB Output is correct
17 Correct 6 ms 55900 KB Output is correct
18 Correct 8 ms 62876 KB Output is correct
19 Correct 8 ms 62812 KB Output is correct
20 Correct 8 ms 62848 KB Output is correct
21 Correct 10 ms 62556 KB Output is correct
22 Correct 9 ms 62300 KB Output is correct
23 Correct 8 ms 62296 KB Output is correct
24 Correct 7 ms 62504 KB Output is correct
25 Correct 6 ms 47708 KB Output is correct
26 Runtime error 1020 ms 1048576 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 45656 KB Output is correct
2 Correct 5 ms 49756 KB Output is correct
3 Correct 5 ms 49752 KB Output is correct
4 Correct 5 ms 49848 KB Output is correct
5 Correct 5 ms 49756 KB Output is correct
6 Correct 5 ms 49756 KB Output is correct
7 Correct 4 ms 43612 KB Output is correct
8 Correct 5 ms 49756 KB Output is correct
9 Correct 5 ms 49752 KB Output is correct
10 Correct 5 ms 49756 KB Output is correct
11 Correct 5 ms 55900 KB Output is correct
12 Correct 5 ms 55900 KB Output is correct
13 Correct 5 ms 55900 KB Output is correct
14 Correct 5 ms 55900 KB Output is correct
15 Correct 6 ms 55900 KB Output is correct
16 Correct 6 ms 55900 KB Output is correct
17 Correct 6 ms 55900 KB Output is correct
18 Correct 8 ms 62876 KB Output is correct
19 Correct 8 ms 62812 KB Output is correct
20 Correct 8 ms 62848 KB Output is correct
21 Correct 10 ms 62556 KB Output is correct
22 Correct 9 ms 62300 KB Output is correct
23 Correct 8 ms 62296 KB Output is correct
24 Correct 7 ms 62504 KB Output is correct
25 Correct 120 ms 100444 KB Output is correct
26 Correct 116 ms 98392 KB Output is correct
27 Correct 114 ms 98552 KB Output is correct
28 Correct 96 ms 87892 KB Output is correct
29 Correct 92 ms 89708 KB Output is correct
30 Correct 95 ms 89172 KB Output is correct
31 Correct 96 ms 89880 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 47964 KB Output is correct
2 Runtime error 919 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 45656 KB Output is correct
2 Correct 5 ms 49756 KB Output is correct
3 Correct 5 ms 49752 KB Output is correct
4 Correct 5 ms 49848 KB Output is correct
5 Correct 5 ms 49756 KB Output is correct
6 Correct 5 ms 49756 KB Output is correct
7 Correct 4 ms 43612 KB Output is correct
8 Correct 5 ms 49756 KB Output is correct
9 Correct 5 ms 49752 KB Output is correct
10 Correct 5 ms 49756 KB Output is correct
11 Correct 5 ms 55900 KB Output is correct
12 Correct 5 ms 55900 KB Output is correct
13 Correct 5 ms 55900 KB Output is correct
14 Correct 5 ms 55900 KB Output is correct
15 Correct 6 ms 55900 KB Output is correct
16 Correct 6 ms 55900 KB Output is correct
17 Correct 6 ms 55900 KB Output is correct
18 Correct 8 ms 62876 KB Output is correct
19 Correct 8 ms 62812 KB Output is correct
20 Correct 8 ms 62848 KB Output is correct
21 Correct 10 ms 62556 KB Output is correct
22 Correct 9 ms 62300 KB Output is correct
23 Correct 8 ms 62296 KB Output is correct
24 Correct 7 ms 62504 KB Output is correct
25 Correct 6 ms 47708 KB Output is correct
26 Runtime error 1020 ms 1048576 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -