Submission #1208956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208956		dima2101	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	200 ms	66188 KiB

Main

#include <bits/stdc++.h>
#define int long long

const int LOGN = 20;

struct DSU
{
    int n;
    std::vector<int> p;

    DSU(int n) : n(n)
    {
        p.resize(n);
        std::iota(p.begin(), p.end(), 0);
    }

    int pred(int a)
    {
        if (a == p[a])
        {
            return a;
        }
        p[a] = pred(p[a]);
        return p[a];
    }
    void mer(int a, int b)
    {
        a = pred(a), b = pred(b);
        if (a == b)
            return;
        p[a] = b;
    }
};

const int MAXN = 2 * 1e5 + 1;
int up[MAXN][LOGN];
int h[MAXN];

void dfs(int v, std::vector<std::vector<int>> &g, int height = 0, int pred = -1)
{
    h[v] = height;
    for (int i = 1; i < LOGN; i++)
    {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for (int u : g[v])
    {
        if (u != pred)
        {
            up[u][0] = v;
            dfs(u, g, height + 1, v);
        }
    }
}

int Dist(int a, int b)
{
    int dist1 = h[a];
    int dist2 = h[b];
    if (h[a] > h[b])
    {
        std::swap(a, b);
    }
    for (int i = LOGN - 1; i >= 0; i--)
    {

        if ((h[b] - h[a]) >= (1 << i))
        {
            b = up[b][i];
        }
    }
    if (a == b)
    {
        return dist1 + dist2 - 2 * h[a];
    }
    for (int i = LOGN - 1; i >= 0; i--)
    {
        if (up[a][i] != up[b][i])
        {
            a = up[a][i];
            b = up[b][i];
        }
    }
    a = up[a][0];
    return dist1 + dist2 - 2 * h[a];
}

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n;
    std::cin >> n;
    std::vector<int> p(n);
    for (int i = 0; i < n; i++)
    {
        std::cin >> p[i];
    }
    std::vector<int> help(n);
    for (int i = 0; i < n; i++)
    {
        p[i]--;
        help[p[i]] = i;
    }

    std::vector<std::vector<int>> g(n);
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        std::cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    up[0][0] = 0;
    dfs(0, g);

    DSU t(n);

    std::vector<int> dp(n, -1);
    for (int v : help)
    {
        dp[v] = 0;
        for (int u : g[v])
        {
            if (dp[u] == -1)
            {
                continue;
            }
            u = t.pred(u);
            dp[v] = std::max(dp[v], dp[u] + Dist(v, u));
            // std::cout << v << ' ' << u << ' ' << Dist(v, u) << std::endl;
            t.mer(u, v);
        }
    }
    std::cout << dp[help.back()];
}

• 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