Submission #1161369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161369		Der_Vlapos	Cat Exercise (JOI23_ho_t4)	C++20	41 / 100	220 ms	74008 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second
#define all(v) v.begin(), v.end()
#define pb push_back

const int BIG = 1e9 + 10;
#define int ll

struct DSU
{
    vector<int> p;
    vector<int> mx;

    void init(int n)
    {
        p.resize(n);
        mx.resize(n);
        for (int i = 0; i < n; ++i)
            p[i] = i;
    }

    int getR(int v)
    {
        return p[v] == v ? v : p[v] = getR(p[v]);
    }

    void merge(int x, int y)
    {
        x = getR(x);
        y = getR(y);
        if (x == y)
            return;
        if (mx[x] > mx[y])
            swap(x, y);
        p[x] = y;
    }
};

struct test
{
    vector<vector<int>> tree, jump;
    vector<int> d, tin, tout;
    int timer = 0;

    void precalc(int v, int pr = -1)
    {
        tin[v] = ++timer;

        for (auto tov : tree[v])
            if (tov != pr)
            {
                d[tov] = d[v] + 1;
                jump[tov][0] = v;
                for (int i = 1; i < 20; ++i)
                {
                    jump[tov][i] = jump[jump[tov][i - 1]][i - 1];
                }
                precalc(tov, v);
            }

        tout[v] = ++timer;
    }

    bool isParent(int x, int y)
    {
        return tin[x] <= tin[y] and tout[y] <= tout[x];
    }

    int lca(int x, int y)
    {
        if (isParent(x, y))
            return x;
        if (isParent(y, x))
            return y;
        for (int i = 19; i >= 0; --i)
            if (!isParent(jump[x][i], y))
                x = jump[x][y];
        return jump[x][0];
    }

    int getD(int x, int y)
    {
        return d[x] + d[y] - 2 * d[lca(x, y)];
    }

    void solve()
    {
        int n;
        cin >> n;
        tree.resize(n);
        jump.resize(n, vector<int>(20));
        d.resize(n);
        tin.resize(n);
        tout.resize(n);
        vector<pii> els;
        vector<int> a(n);
        for (int i = 0; i < n; ++i)
        {
            int x;
            cin >> x;
            els.pb({x, i});
            a[i] = x;
        }
        sort(all(els));
        tree.resize(n);
        for (int i = 1; i < n; ++i)
        {
            int x, y;
            cin >> x >> y;
            --x, --y;
            tree[x].pb(y);
            tree[y].pb(x);
        }
        precalc(0);
        vector<int> res(n);

        DSU dsu;
        dsu.init(n);
        for (int i = 0; i < n; ++i)
            dsu.mx[i] = a[i];

        for (auto [val, v] : els)
        {
            int curMx = 0;
            for (auto tov : tree[v])
                if (a[tov] < a[v])
                {
                    int nextV = dsu.getR(tov);
                    curMx = max(curMx, res[nextV] + getD(nextV, v));
                }

            res[v] = curMx;
            for (auto tov : tree[v])
                if (a[tov] < a[v])
                {
                    dsu.merge(v, tov);
                }

            if (val == n)
                cout << res[v] << "\n";
        }
    }
};

main()
{
    test t;
    t.solve();
}

Compilation message (stderr)

Main.cpp:151:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  151 | main()
      | ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 10
• Subtask 5: 20 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26