oj.uz

Submission #861722

# Submission time Handle Problem Language Result Execution time Memory
861722 2023-10-16T18:19:20 Z arbuzick Cat Exercise (JOI23_ho_t4) C++17
31 / 100
 2000 ms 47672 KB 
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx,avx2")
#include <bits/stdc++.h>

using namespace std;

struct DSU {
    int n;
    vector<int> sz, p;

    DSU(int _n) {
        n = _n;
        sz.assign(n, 1);
        p.resize(n);
        iota(p.begin(), p.end(), 0);
    }

    int pr(int v) {
        if (p[v] == v) {
            return v;
        }
        return p[v] = pr(p[v]);
    }

    void unite(int a, int b) {
        a = pr(a), b = pr(b);
        if (a == b) {
            return;
        }
        if (sz[a] < sz[b]) {
            swap(a, b);
        }
        p[b] = a;
        sz[a] += sz[b];
    }
};

constexpr int maxn = 2e5 + 5, lg = 20;

vector<int> g[maxn];

int go[lg][maxn];

int tin[maxn], tout[maxn];

int t = 0;

int d[maxn];

void dfs(int v) {
    tin[v] = t;
    t++;
    for (auto u : g[v]) {
        if (u != go[0][v]) {
            go[0][u] = v;
            d[u] = d[v] + 1;
            dfs(u);
        }
    }
    tout[v] = t;
}

int lca(int a, int b) {
    if (tin[a] <= tin[b] && tout[b] <= tout[a]) {
        return a;
    }
    if (tin[b] <= tin[a] && tout[a] <= tout[b]) {
        return b;
    }
    int v = a;
    for (int i = lg - 1; i >= 0; --i) {
        if (!(tin[go[i][v]] <= tin[b] && tout[b] <= tout[go[i][v]])) {
            v = go[i][v];
        }
    }
    return go[0][v];
}

int get_dist(int a, int b) {
    return d[a] + d[b] - d[lca(a, b)] * 2;
}

void solve() {
    int n;
    cin >> n;
    vector<int> p(n);
    vector<pair<int, int>> ord(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
        ord[i] = {p[i], i};
    }
    sort(ord.begin(), ord.end());
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(0);
    for (int i = 1; i < lg; ++i) {
        for (int j = 0; j < n; ++j) {
            go[i][j] = go[i - 1][go[i - 1][j]];
        }
    }
    vector<long long> dp(n);
    long long ans = 0;
    for (int i = n - 1; i >= 0; --i) {
        DSU d(n);
        for (auto j : g[ord[i].second]) {
            d.unite(ord[i].second, j);
        }
        for (int j = 0; j < i; ++j) {
            for (auto k : g[ord[j].second]) {
                if (p[k] < ord[j].first) {
                    d.unite(ord[j].second, k);
                }
            }
        }
        for (int j = 0; j < i; ++j) {
            if (d.pr(ord[i].second) == d.pr(ord[j].second)) {
                dp[j] = max(dp[j], dp[i] + get_dist(ord[i].second, ord[j].second));
                ans = max(ans, dp[j]);
            }
        }
    }
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 4 ms 18780 KB Output is correct
6 Correct 4 ms 18780 KB Output is correct
7 Correct 4 ms 18776 KB Output is correct
8 Correct 4 ms 18780 KB Output is correct
9 Correct 3 ms 18780 KB Output is correct
10 Correct 3 ms 18776 KB Output is correct
11 Correct 4 ms 18780 KB Output is correct
12 Correct 5 ms 18776 KB Output is correct
13 Correct 4 ms 18780 KB Output is correct
14 Correct 4 ms 18780 KB Output is correct
15 Correct 4 ms 18780 KB Output is correct
16 Correct 4 ms 19032 KB Output is correct
17 Correct 4 ms 18780 KB Output is correct
18 Correct 174 ms 19604 KB Output is correct
19 Correct 184 ms 19596 KB Output is correct
20 Correct 185 ms 19544 KB Output is correct
21 Correct 245 ms 19548 KB Output is correct
22 Correct 257 ms 19604 KB Output is correct
23 Correct 240 ms 19596 KB Output is correct
24 Correct 240 ms 19600 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 4 ms 18780 KB Output is correct
6 Correct 4 ms 18780 KB Output is correct
7 Correct 4 ms 18776 KB Output is correct
8 Correct 4 ms 18780 KB Output is correct
9 Correct 3 ms 18780 KB Output is correct
10 Correct 3 ms 18776 KB Output is correct
11 Correct 4 ms 18780 KB Output is correct
12 Correct 5 ms 18776 KB Output is correct
13 Correct 4 ms 18780 KB Output is correct
14 Correct 4 ms 18780 KB Output is correct
15 Correct 4 ms 18780 KB Output is correct
16 Correct 4 ms 19032 KB Output is correct
17 Correct 4 ms 18780 KB Output is correct
18 Correct 174 ms 19604 KB Output is correct
19 Correct 184 ms 19596 KB Output is correct
20 Correct 185 ms 19544 KB Output is correct
21 Correct 245 ms 19548 KB Output is correct
22 Correct 257 ms 19604 KB Output is correct
23 Correct 240 ms 19596 KB Output is correct
24 Correct 240 ms 19600 KB Output is correct
25 Correct 3 ms 18776 KB Output is correct
26 Correct 549 ms 19456 KB Output is correct
27 Correct 357 ms 19488 KB Output is correct
28 Correct 578 ms 19444 KB Output is correct
29 Correct 289 ms 19548 KB Output is correct
30 Correct 361 ms 19300 KB Output is correct
31 Correct 409 ms 19304 KB Output is correct
32 Correct 362 ms 19300 KB Output is correct
33 Correct 404 ms 19300 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 4 ms 18780 KB Output is correct
6 Correct 4 ms 18780 KB Output is correct
7 Correct 4 ms 18776 KB Output is correct
8 Correct 4 ms 18780 KB Output is correct
9 Correct 3 ms 18780 KB Output is correct
10 Correct 3 ms 18776 KB Output is correct
11 Correct 4 ms 18780 KB Output is correct
12 Correct 5 ms 18776 KB Output is correct
13 Correct 4 ms 18780 KB Output is correct
14 Correct 4 ms 18780 KB Output is correct
15 Correct 4 ms 18780 KB Output is correct
16 Correct 4 ms 19032 KB Output is correct
17 Correct 4 ms 18780 KB Output is correct
18 Correct 174 ms 19604 KB Output is correct
19 Correct 184 ms 19596 KB Output is correct
20 Correct 185 ms 19544 KB Output is correct
21 Correct 245 ms 19548 KB Output is correct
22 Correct 257 ms 19604 KB Output is correct
23 Correct 240 ms 19596 KB Output is correct
24 Correct 240 ms 19600 KB Output is correct
25 Execution timed out 2097 ms 47672 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18780 KB Output is correct
2 Correct 4 ms 18780 KB Output is correct
3 Execution timed out 2068 ms 35388 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 4 ms 18780 KB Output is correct
6 Correct 4 ms 18780 KB Output is correct
7 Correct 4 ms 18776 KB Output is correct
8 Correct 4 ms 18780 KB Output is correct
9 Correct 3 ms 18780 KB Output is correct
10 Correct 3 ms 18776 KB Output is correct
11 Correct 4 ms 18780 KB Output is correct
12 Correct 5 ms 18776 KB Output is correct
13 Correct 4 ms 18780 KB Output is correct
14 Correct 4 ms 18780 KB Output is correct
15 Correct 4 ms 18780 KB Output is correct
16 Correct 4 ms 19032 KB Output is correct
17 Correct 4 ms 18780 KB Output is correct
18 Correct 174 ms 19604 KB Output is correct
19 Correct 184 ms 19596 KB Output is correct
20 Correct 185 ms 19544 KB Output is correct
21 Correct 245 ms 19548 KB Output is correct
22 Correct 257 ms 19604 KB Output is correct
23 Correct 240 ms 19596 KB Output is correct
24 Correct 240 ms 19600 KB Output is correct
25 Correct 3 ms 18776 KB Output is correct
26 Correct 549 ms 19456 KB Output is correct
27 Correct 357 ms 19488 KB Output is correct
28 Correct 578 ms 19444 KB Output is correct
29 Correct 289 ms 19548 KB Output is correct
30 Correct 361 ms 19300 KB Output is correct
31 Correct 409 ms 19304 KB Output is correct
32 Correct 362 ms 19300 KB Output is correct
33 Correct 404 ms 19300 KB Output is correct
34 Execution timed out 2097 ms 47672 KB Time limit exceeded
35 Halted 0 ms 0 KB -