Submission #1256535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256535		chikien2009	Cat Exercise (JOI23_ho_t4)	C++20	100 / 100	422 ms	40352 KiB

Main

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, c[200000], a, b, sp[20][200000], depth[200000], pre[200000], sz[200000], v[200000];
long long f[200000];
vector<int> g[200000];
pair<int, int> p[200000];

inline void DFS(int node, int par)
{
    sp[0][node] = par;
    for (int i = 1; i < 20; ++i)
    {
        sp[i][node] = sp[i - 1][sp[i - 1][node]];
    }
    for (auto & i : g[node])
    {
        if (i != par)
        {
            depth[i] = depth[node] + 1;
            DFS(i, node);
        }
    }
}

inline int LCA(int ina, int inb)
{
    if (depth[ina] != depth[inb])
    {
        if (depth[ina] < depth[inb])
        {
            swap(ina, inb);
        }
        for (int i = 19; i >= 0; --i)
        {
            if (depth[sp[i][ina]] >= depth[inb])
            {
                ina = sp[i][ina];
            }
        }
    }
    if (ina == inb)
    {
        return ina;
    }
    for (int i = 19; i >= 0; --i)
    {
        if (sp[i][ina] != sp[i][inb])
        {
            ina = sp[i][ina];
            inb = sp[i][inb];
        }
    }
    return sp[0][ina];
}

inline int Dist(int ina, int inb)
{
    int lca = LCA(ina, inb);
    return depth[ina] + depth[inb] - 2 * depth[lca];
}

inline int Get(int inp)
{
    return (inp == pre[inp] ? inp : pre[inp] = Get(pre[inp]));
}

int main()
{
    setup();

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> c[i];
        p[i] = {c[i], i};
        pre[i] = i;
        sz[i] = 1;
        v[i] = i;
    }
    for (int i = 1; i < n; ++i)
    {
        cin >> a >> b;
        g[a - 1].push_back(b - 1);
        g[b - 1].push_back(a - 1);
    }
    sort(p, p + n);
    DFS(0, 0);
    for (int i = 0, x; i < n; ++i)
    {
        x = p[i].second;
        for (auto & y : g[x])
        {
            if (c[x] > c[y])
            {
                a = Get(x);
                b = Get(y);
                f[x] = max(f[x], f[v[b]] + Dist(x, v[b]));
                if (sz[a] < sz[b])
                {
                    swap(a, b);
                }
                sz[a] += sz[b];
                v[a] = x;
                pre[b] = a;
            }
        }   
    }   
    cout << (*max_element(f, f + 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