Submission #916510

#	Time	Username	Problem	Language	Result	Execution time	Memory
916510		GrandTiger1729	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	536 ms	95228 KiB

Main

#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<long long> 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 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 23 / 23
• Subtask 7: 26 / 26