oj.uz

Submission #1038459

# Submission time Handle Problem Language Result Execution time Memory
1038459 2024-07-29T20:06:17 Z SoulKnight Cat Exercise (JOI23_ho_t4) C++17
41 / 100
 117 ms 99668 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];
bool used[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){
    used[u] = 1;

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

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

        ll 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),
                       [&](ll x, ll y){return p[x] < p[y];});
        // cout << "llo " << nxt << ln;
        if (!used[nxt] && nxt) res = max(res, dist(u, nxt) + f(nxt, v, btm));
    }

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

    ll nxt;
    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 (!used[nxt] && nxt) res = max(res, dist(u, nxt) + f(nxt, tp, u));

    used[u] = 0;
    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 5 ms 45400 KB Output is correct
2 Correct 5 ms 49496 KB Output is correct
3 Correct 5 ms 49500 KB Output is correct
4 Correct 5 ms 49500 KB Output is correct
5 Correct 5 ms 49644 KB Output is correct
6 Correct 5 ms 49500 KB Output is correct
7 Correct 4 ms 43356 KB Output is correct
8 Correct 5 ms 49500 KB Output is correct
9 Correct 5 ms 49500 KB Output is correct
10 Correct 5 ms 49500 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 45400 KB Output is correct
2 Correct 5 ms 49496 KB Output is correct
3 Correct 5 ms 49500 KB Output is correct
4 Correct 5 ms 49500 KB Output is correct
5 Correct 5 ms 49644 KB Output is correct
6 Correct 5 ms 49500 KB Output is correct
7 Correct 4 ms 43356 KB Output is correct
8 Correct 5 ms 49500 KB Output is correct
9 Correct 5 ms 49500 KB Output is correct
10 Correct 5 ms 49500 KB Output is correct
11 Correct 5 ms 55644 KB Output is correct
12 Correct 5 ms 55900 KB Output is correct
13 Correct 5 ms 55828 KB Output is correct
14 Correct 5 ms 55644 KB Output is correct
15 Correct 5 ms 55644 KB Output is correct
16 Correct 5 ms 55644 KB Output is correct
17 Correct 5 ms 55644 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 45400 KB Output is correct
2 Correct 5 ms 49496 KB Output is correct
3 Correct 5 ms 49500 KB Output is correct
4 Correct 5 ms 49500 KB Output is correct
5 Correct 5 ms 49644 KB Output is correct
6 Correct 5 ms 49500 KB Output is correct
7 Correct 4 ms 43356 KB Output is correct
8 Correct 5 ms 49500 KB Output is correct
9 Correct 5 ms 49500 KB Output is correct
10 Correct 5 ms 49500 KB Output is correct
11 Correct 5 ms 55644 KB Output is correct
12 Correct 5 ms 55900 KB Output is correct
13 Correct 5 ms 55828 KB Output is correct
14 Correct 5 ms 55644 KB Output is correct
15 Correct 5 ms 55644 KB Output is correct
16 Correct 5 ms 55644 KB Output is correct
17 Correct 5 ms 55644 KB Output is correct
18 Correct 8 ms 64604 KB Output is correct
19 Correct 8 ms 64600 KB Output is correct
20 Correct 8 ms 64492 KB Output is correct
21 Correct 9 ms 64348 KB Output is correct
22 Correct 8 ms 64224 KB Output is correct
23 Correct 8 ms 64348 KB Output is correct
24 Correct 8 ms 64348 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 45400 KB Output is correct
2 Correct 5 ms 49496 KB Output is correct
3 Correct 5 ms 49500 KB Output is correct
4 Correct 5 ms 49500 KB Output is correct
5 Correct 5 ms 49644 KB Output is correct
6 Correct 5 ms 49500 KB Output is correct
7 Correct 4 ms 43356 KB Output is correct
8 Correct 5 ms 49500 KB Output is correct
9 Correct 5 ms 49500 KB Output is correct
10 Correct 5 ms 49500 KB Output is correct
11 Correct 5 ms 55644 KB Output is correct
12 Correct 5 ms 55900 KB Output is correct
13 Correct 5 ms 55828 KB Output is correct
14 Correct 5 ms 55644 KB Output is correct
15 Correct 5 ms 55644 KB Output is correct
16 Correct 5 ms 55644 KB Output is correct
17 Correct 5 ms 55644 KB Output is correct
18 Correct 8 ms 64604 KB Output is correct
19 Correct 8 ms 64600 KB Output is correct
20 Correct 8 ms 64492 KB Output is correct
21 Correct 9 ms 64348 KB Output is correct
22 Correct 8 ms 64224 KB Output is correct
23 Correct 8 ms 64348 KB Output is correct
24 Correct 8 ms 64348 KB Output is correct
25 Correct 5 ms 47452 KB Output is correct
26 Correct 8 ms 64504 KB Output is correct
27 Correct 9 ms 64344 KB Output is correct
28 Correct 9 ms 64348 KB Output is correct
29 Incorrect 10 ms 64388 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 5 ms 45400 KB Output is correct
2 Correct 5 ms 49496 KB Output is correct
3 Correct 5 ms 49500 KB Output is correct
4 Correct 5 ms 49500 KB Output is correct
5 Correct 5 ms 49644 KB Output is correct
6 Correct 5 ms 49500 KB Output is correct
7 Correct 4 ms 43356 KB Output is correct
8 Correct 5 ms 49500 KB Output is correct
9 Correct 5 ms 49500 KB Output is correct
10 Correct 5 ms 49500 KB Output is correct
11 Correct 5 ms 55644 KB Output is correct
12 Correct 5 ms 55900 KB Output is correct
13 Correct 5 ms 55828 KB Output is correct
14 Correct 5 ms 55644 KB Output is correct
15 Correct 5 ms 55644 KB Output is correct
16 Correct 5 ms 55644 KB Output is correct
17 Correct 5 ms 55644 KB Output is correct
18 Correct 8 ms 64604 KB Output is correct
19 Correct 8 ms 64600 KB Output is correct
20 Correct 8 ms 64492 KB Output is correct
21 Correct 9 ms 64348 KB Output is correct
22 Correct 8 ms 64224 KB Output is correct
23 Correct 8 ms 64348 KB Output is correct
24 Correct 8 ms 64348 KB Output is correct
25 Correct 104 ms 97620 KB Output is correct
26 Correct 109 ms 99668 KB Output is correct
27 Correct 117 ms 99668 KB Output is correct
28 Correct 93 ms 92036 KB Output is correct
29 Correct 100 ms 94012 KB Output is correct
30 Correct 93 ms 93140 KB Output is correct
31 Correct 100 ms 93776 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 47704 KB Output is correct
2 Incorrect 6 ms 55644 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 45400 KB Output is correct
2 Correct 5 ms 49496 KB Output is correct
3 Correct 5 ms 49500 KB Output is correct
4 Correct 5 ms 49500 KB Output is correct
5 Correct 5 ms 49644 KB Output is correct
6 Correct 5 ms 49500 KB Output is correct
7 Correct 4 ms 43356 KB Output is correct
8 Correct 5 ms 49500 KB Output is correct
9 Correct 5 ms 49500 KB Output is correct
10 Correct 5 ms 49500 KB Output is correct
11 Correct 5 ms 55644 KB Output is correct
12 Correct 5 ms 55900 KB Output is correct
13 Correct 5 ms 55828 KB Output is correct
14 Correct 5 ms 55644 KB Output is correct
15 Correct 5 ms 55644 KB Output is correct
16 Correct 5 ms 55644 KB Output is correct
17 Correct 5 ms 55644 KB Output is correct
18 Correct 8 ms 64604 KB Output is correct
19 Correct 8 ms 64600 KB Output is correct
20 Correct 8 ms 64492 KB Output is correct
21 Correct 9 ms 64348 KB Output is correct
22 Correct 8 ms 64224 KB Output is correct
23 Correct 8 ms 64348 KB Output is correct
24 Correct 8 ms 64348 KB Output is correct
25 Correct 5 ms 47452 KB Output is correct
26 Correct 8 ms 64504 KB Output is correct
27 Correct 9 ms 64344 KB Output is correct
28 Correct 9 ms 64348 KB Output is correct
29 Incorrect 10 ms 64388 KB Output isn't correct
30 Halted 0 ms 0 KB -