제출 #960988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
960988		Andrei_ierdnA	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	145 ms	62544 KiB

Main

#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

int n, i, h[200010], u, v, p[200010], depth[200010];
vector<int> nb[200010];
long long dp[200010];

namespace euler
{
    int t, sparseMin[19][400010], firstPoz[200010];
    void appendNode(int node)
    {
        sparseMin[0][++t] = depth[node];
    }
    void appendNodeFirst(int node)
    {
        appendNode(node);
        firstPoz[node] = t;
    }
    void computeSparse()
    {
        for (int i = 1; (1 << i) <= t; i++) {
            for (int j = 1; j + (1 << i) - 1 <= t; j++) {
                sparseMin[i][j] = min(sparseMin[i-1][j], sparseMin[i-1][j+(1<<(i-1))]);
            }
        }
    }
    int querySparseMin(int l, int r)
    {
        int len = 31 - __builtin_clz(r-l+1);
        return min(sparseMin[len][l], sparseMin[len][r-(1<<len)+1]);
    }
    int getNodeDist(int a, int b)
    {
        int minDepth = querySparseMin(min(firstPoz[a], firstPoz[b]), max(firstPoz[a], firstPoz[b]));
        return depth[a] + depth[b] - 2*minDepth;
    }
}

namespace dsu
{
    int nrdsu, dsu[200010], maxi[200010];
    void init()
    {
        nrdsu = n;
        for (int i = 1; i <= n; i++) {
            dsu[i] = -1;
            maxi[i] = i;
        }
    }
    int getRoot(int node)
    {
        if (dsu[node] < 0) return node;
        return dsu[node] = getRoot(dsu[node]);
    }
    bool dsuMerge(int a, int b)
    {
        a = getRoot(a);
        b = getRoot(b);
        if (a == b) return false;
        if (dsu[a] > dsu[b]) swap(a, b);
        dsu[a] += dsu[b];
        dsu[b] = a;
        maxi[a] = max(maxi[a], maxi[b]);
        maxi[b] = 0;
        nrdsu--;
        return true;
    }
}

void dfs1(int node)
{
    euler::appendNodeFirst(node);
    for (auto x : nb[node]) {
        if (!p[x]) {
            p[x] = node;
            depth[x] = depth[node] + 1;
            dfs1(x);
            euler::appendNode(node);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> h[i];
    }
    for (i = 1; i < n; i++) {
        cin >> u >> v;
        u = h[u];
        v = h[v];
        nb[u].push_back(v);
        nb[v].push_back(u);
    }
    p[1] = 1;
    depth[1] = 1;
    dfs1(1);
    euler::computeSparse();
    dsu::init();
    dp[1] = 0;
    for (int i = 2; i <= n; i++) {
        for (auto x : nb[i]) {
            if (x <= i) {
                int bigboy = dsu::maxi[dsu::getRoot(x)];
                dp[i] = max(dp[i], euler::getNodeDist(i, bigboy) + dp[bigboy]);
                dsu::dsuMerge(i, x);
            }
        }
    }
    cout << dp[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