Submission #931540

#	Time	Username	Problem	Language	Result	Execution time	Memory
931540		Pring	Cat Exercise (JOI23_ho_t4)	C++14	100 / 100	512 ms	123780 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
#define debug(x...) cout << "[" << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 400005, INF = 2e9;
int n, a[MXN];
vector<int> edge[MXN];
int pos[MXN], p[MXN], C = 0;
pii fl[MXN];
vector<pii> edu[MXN];
bitset<MXN> ban;

struct SMG {
    int val[MXN * 4], tag[MXN * 4];
    void add_tag(int id, int t) {
        val[id] += t;
        tag[id] += t;
    }
    void push(int id) {
        if (tag[id] == 0) return;
        add_tag(id * 2 + 1, tag[id]);
        add_tag(id * 2 + 2, tag[id]);
        tag[id] = 0;
    }
    void pull(int id) {
        val[id] = max(val[id * 2 + 1], val[id * 2 + 2]);
    }
    void init(int n) {
        fill(val, val + 4 * n, 0);
        fill(tag, tag + 4 * n, 0);
    }
    void modify(int id, int l, int r, int _l, int _r, int v) {
        if (_r <= l || r <= _l) return;
        if (_l <= l && r <= _r) {
            add_tag(id, v);
            return;
        }
        int mid = (l + r) >> 1;
        push(id);
        modify(id * 2 + 1, l, mid, _l, _r, v);
        modify(id * 2 + 2, mid, r, _l, _r, v);
        pull(id);
    }
    int query(int id, int l, int r, int _l, int _r) {
        if (_r <= l || r <= _l) return INT_MIN;
        if (_l <= l && r <= _r) return val[id];
        int mid = (l + r) >> 1;
        push(id);
        return max(query(id * 2 + 1, l, mid, _l, _r), query(id * 2 + 2, mid, r, _l, _r));
    }
    void DFS(int id, int l, int r) {
        if (l + 1 == r) {
            cout << (val[id] <= 0 ? -1 : val[id]) << ' ';
            return;
        }
        int mid = (l + r) >> 1;
        push(id);
        DFS(id * 2 + 1, l, mid);
        DFS(id * 2 + 2, mid, r);
    }
} smg;

namespace LEN {
    vector<int> v;
    SMG smg;
    int pos[MXN], d[MXN], n;

    void DFS(int id, int par, int dep) {
        pos[id] = v.size();
        d[id] = dep;
        v.push_back(dep);
        for (auto &i : edge[id]) {
            if (i == par) continue;
            DFS(i, id, dep + 1);
            v.push_back(dep);
        }
    }

    void BUILD(int rt) {
        DFS(rt, 0, 0);
        n = v.size();
        smg.init(n);
        FOR(i, 0, n) smg.modify(0, 0, n, i, i + 1, -v[i]);
    }

    int calc(int l, int r) {
        if (pos[l] > pos[r]) swap(l, r);
        return d[l] + d[r] + 2 * smg.query(0, 0, n, pos[l], pos[r] + 1);
    }
}

void FLAT(int id, int par) {
    fl[id].fs = C++;
    p[id] = par;
    for (auto &i : edge[id]) {
        if (i == par) continue;
        FLAT(i, id);
    }
    fl[id].sc = C;
}

void BAN(int id) {
    // debug("BAN", id, fl[id].fs, fl[id].sc);
    smg.modify(0, 0, n, fl[id].fs, fl[id].sc, -INF);
}

void UNBAN(int id) {
    smg.modify(0, 0, n, fl[id].fs, fl[id].sc, INF);
}

void EDU_PUSH(int x, int y, int l) {
    edu[x].push_back(mp(l, y));
}

int solve(int id, int rt) {
    // debug(id, rt);
    // smg.DFS(0, 0, n);
    // cout << endl;
    if (id == 0) return 0;
    int ct = smg.query(0, 0, n, fl[id].fs, fl[id].sc);
    if (ct <= 0) return 0;
    ct = pos[ct];
    // debug(ct);
    ban[ct] = true;
    BAN(ct);
    int pp = solve(rt, rt);
    if (pp) EDU_PUSH(ct, pp, LEN::calc(ct, pp));
    UNBAN(ct);
    for (auto &i : edge[ct]) {
        if (i == p[ct]) continue;
        if (ban[i]) continue;
        int pp = solve(i, i);
        EDU_PUSH(ct, pp, LEN::calc(ct, pp));
    }
    return ct;
}

int eduroam(int id) {
    int ans = 0;
    for (auto &i : edu[id]) {
        ans = max(ans, i.fs + eduroam(i.sc));
    }
    return ans;
}

void miku() {
    int x, y;
    cin >> n;
    FOR(i, 1, n + 1) {
        cin >> a[i];
        pos[a[i]] = i;
    }
    FOR(i, 1, n) {
        cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    LEN::BUILD(1);
    // debug(LEN::calc(3, 5));
    // LEN::calc(3, 5);
    FLAT(1, 0);
    smg.init(n);
    FOR(i, 1, n + 1) smg.modify(0, 0, n, fl[i].fs, fl[i].fs + 1, a[i]);
    int rt = solve(1, 1);
    // FOR(i, 1, n + 1) {
    //     for (auto &j : edu[i]) cout << '<' << j.fs << ' ' << j.sc << "> ";
    //     cout << '\n';
    // }
    cout << eduroam(rt) << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(iostream::failbit);
    miku();
    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