제출 #1254057

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254057		norman165	Cat Exercise (JOI23_ho_t4)	C++20	0 / 100	0 ms	328 KiB

Main

#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int long long
#define yes() cout << "YES\n"
#define no() cout << "NO\n"

using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

const int inf = 1e18;
const int mod = 1e9 + 7;
const int maxn = 1e7 + 5e6;
const int mod1 = 998244353;
const int mod2 = 1e18 + 1;
const int mod3 = 1e9 + 9;
const int mod4 = 333333333;
const int mod5 = 200000;
const int mod6 = 10007;
const int k = 300;
const int w = 1e5;
const ld EPS = 1e-8;

int LOG = 30;

vector<vector<int>> g;
vector<int> h;
vector<int> tin, tout;
vector<vector<int>> up;
vector<int> dp;
int timer = 1;

void precalc(int v, int p, int d) {
    h[v] = d;
    tin[v] = timer++;

    up[v][0] = p;
    for (int i = 1; i < LOG; i++) up[v][i] = up[up[v][i - 1]][i - 1];

    for (int& u : g[v]) {
        if (u != p) {
            precalc(u, v, d + 1);
        }
    }

    tout[v] = timer++;
}

bool anc(int a, int b) {
    return tin[a] <= tin[b] && tout[b] <= tout[a];
}

int lca(int a, int b) {
    if (anc(a, b)) return a;
    if (anc(b, a)) return b;

    for (int i = LOG - 1; i >= 0; i--) {
        if (!anc(up[a][i], b)) a = up[a][i];
    }

    return up[a][0];
}

int get(int a, int b) {
    int l = lca(a, b);
    return h[a] + h[b] - 2 * h[l];
}

struct DSU {
    vector<int> p, c;
    int n;

    DSU(vector<int>& b) {
        n = b.size();
        p.assign(n, 0);
        c = b;

        iota(all(p), 0ll);
    }

    int get(int x) {
        if (p[x] == x) return x;
        return p[x] = get(p[x]);
    }

    void unite(int a, int b) {
        a = get(a), b = get(b);
        if (a == b) return;

        if (c[a] < c[b]) swap(a, b);
        p[b] = a;
    }

    int get1(int x) {
        x = get(x);
        return c[x];
    }
};

void solve() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int& i : a) cin >> i;
    g.assign(n, vector<int> ());
    dp.assign(n, 0);
    tin.assign(n, 0);
    tout.assign(n, 0);
    h.assign(n, 0);
    up.assign(n, vector<int> (LOG));

    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);
    }

    precalc(0, 0, 0);
    DSU dsu(a);

    vector<int> p(n);
    iota(all(p), 0ll);

    sort(all(p), [&](int i, int j) {
        return a[i] < a[j];
    });

    for (int& v : p) {
        int idx = -1;

        for (int& u : g[v]) {
            int g = dsu.get1(u);
            int cand = dsu.get(u);
            if (g < a[v]) {
                if (idx == -1 || dp[idx] < dp[cand]) {
                    idx = cand;
                }
            }
        }

        if (idx == -1) continue;
        dp[v] += dp[idx] + get(v, idx);
        dsu.unite(idx, v);
    }

    cout << dp[p.back()] << "\n";
}

signed main() {
    // cout.precision(16);

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;

    while (t--) {
        solve();
    }
}

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