oj.uz

Submission #916509

# Submission time Handle Problem Language Result Execution time Memory
916509 2024-01-26T03:13:06 Z GrandTiger1729 Cat Exercise (JOI23_ho_t4) C++17
54 / 100
 238 ms 93780 KB 
#include <bits/stdc++.h>
using namespace std;

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        a[i]--;
    }
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> dep(n);
    vector<vector<int>> up(n, vector<int>(__lg(n) + 1));
    {
        vector<bool> vis(n);
        function<void(int)> dfs = [&](int u)
        {
            vis[u] = 1;
            for (auto &v : g[u])
            {
                if (!vis[v])
                {
                    dep[v] = dep[u] + 1;
                    dfs(v);
                    up[v][0] = u;
                }
            }
        };
        dfs(0);
        for (int i = 1; i <= __lg(n); i++)
        {
            for (int u = 0; u < n; u++)
            {
                up[u][i] = up[up[u][i - 1]][i - 1];
            }
        }
    }
    auto lca = [&](int u, int v)
    {
        if (dep[u] < dep[v])
        {
            swap(u, v);
        }
        for (int i = __lg(n); i >= 0; i--)
        {
            if (dep[up[u][i]] >= dep[v])
            {
                u = up[u][i];
            }
        }
        if (u == v)
        {
            return u;
        }
        for (int i = __lg(n); i >= 0; i--)
        {
            if (up[u][i] != up[v][i])
            {
                u = up[u][i];
                v = up[v][i];
            }
        }
        return up[u][0];
    };
    auto dis = [&](int u, int v)
    {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    };
    vector<vector<pair<int, int>>> G(n);
    {
        int rt = find(a.begin(), a.end(), n - 1) - a.begin();
        vector<bool> vis(n);
        function<set<pair<int, int>>(int)> dfs = [&](int u) -> set<pair<int, int>>
        {
            set<pair<int, int>> ret;
            ret.emplace(a[u], u);
            vis[u] = 1;
            for (auto &v : g[u])
            {
                if (!vis[v])
                {
                    auto st = dfs(v);
                    st.emplace(a[u], u);
                    while (st.size() >= 2 && st.begin()->first < a[u])
                    {
                        auto x = *st.begin();
                        st.erase(st.begin());
                        auto y = *st.begin();
                        G[y.first].emplace_back(x.first, dis(y.second, x.second));
                    }
                    if (ret.size() < st.size())
                    {
                        swap(ret, st);
                    }
                    for (auto &x : st)
                    {
                        ret.insert(x);
                    }
                }
            }
            return ret;
        };
        dfs(rt);
    }
    vector<int> vis(n);
    vector<int> dp(n);
    function<void(int)> dfs = [&](int u)
    {
        vis[u] = 1;
        for (auto &[v, w] : G[u])
        {
            if (!vis[v])
            {
                dfs(v);
                dp[u] = max(dp[u], dp[v] + w);
            }
        }
    };
    dfs(n - 1);
    cout << dp[n - 1] << '\n';
    return 0;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 388 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 4 ms 2652 KB Output is correct
19 Correct 4 ms 2652 KB Output is correct
20 Correct 5 ms 2652 KB Output is correct
21 Correct 4 ms 2392 KB Output is correct
22 Correct 4 ms 2140 KB Output is correct
23 Correct 4 ms 2132 KB Output is correct
24 Correct 4 ms 1880 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 388 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 4 ms 2652 KB Output is correct
19 Correct 4 ms 2652 KB Output is correct
20 Correct 5 ms 2652 KB Output is correct
21 Correct 4 ms 2392 KB Output is correct
22 Correct 4 ms 2140 KB Output is correct
23 Correct 4 ms 2132 KB Output is correct
24 Correct 4 ms 1880 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 5 ms 2140 KB Output is correct
27 Correct 7 ms 2396 KB Output is correct
28 Correct 5 ms 2516 KB Output is correct
29 Correct 5 ms 2396 KB Output is correct
30 Correct 4 ms 1444 KB Output is correct
31 Correct 5 ms 1368 KB Output is correct
32 Correct 4 ms 1372 KB Output is correct
33 Correct 4 ms 1496 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 388 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 4 ms 2652 KB Output is correct
19 Correct 4 ms 2652 KB Output is correct
20 Correct 5 ms 2652 KB Output is correct
21 Correct 4 ms 2392 KB Output is correct
22 Correct 4 ms 2140 KB Output is correct
23 Correct 4 ms 2132 KB Output is correct
24 Correct 4 ms 1880 KB Output is correct
25 Incorrect 238 ms 93780 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 231 ms 48696 KB Output is correct
4 Correct 224 ms 48976 KB Output is correct
5 Correct 224 ms 48740 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 388 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 4 ms 2652 KB Output is correct
19 Correct 4 ms 2652 KB Output is correct
20 Correct 5 ms 2652 KB Output is correct
21 Correct 4 ms 2392 KB Output is correct
22 Correct 4 ms 2140 KB Output is correct
23 Correct 4 ms 2132 KB Output is correct
24 Correct 4 ms 1880 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 5 ms 2140 KB Output is correct
27 Correct 7 ms 2396 KB Output is correct
28 Correct 5 ms 2516 KB Output is correct
29 Correct 5 ms 2396 KB Output is correct
30 Correct 4 ms 1444 KB Output is correct
31 Correct 5 ms 1368 KB Output is correct
32 Correct 4 ms 1372 KB Output is correct
33 Correct 4 ms 1496 KB Output is correct
34 Incorrect 238 ms 93780 KB Output isn't correct
35 Halted 0 ms 0 KB -