Submission #1117945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117945		macneil	Cat Exercise (JOI23_ho_t4)	C++17	100 / 100	412 ms	184804 KiB

Main

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <bitset>
#include <iterator>
#include <iomanip>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <random>
#include <cassert>

using namespace std;

#define int long long
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

typedef long long ll;
typedef long double ld;

struct DSU {
    vector<set<int>> lol;
    vector<int> p;

    DSU(vector<set<int>> lol, int n) : lol(lol) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
    }

    int gt(int a) {
        while (p[a] != a) a = p[a] = p[p[a]];
        return a;
    }

    void unite(int a, int b) {
        a = gt(a);
        b = gt(b);
        if (a == b) return;
        if (lol[a].size() < lol[b].size()) swap(a, b);
        for (auto e : lol[b]) lol[a].insert(e);
        p[b] = a;
    }

    int ans(int a, int x) {
        a = gt(a);
        // cout << x << '\n';
        // for (auto e : lol[a]) cout << e << ' ';
        // cout << endl;
        return (*lol[a].upper_bound(x));
    }
};

struct SparseTable {
    vector<vector<int>> sp;

    SparseTable(){}

    void build(vector<int> a) {
        int n = a.size();
        int lg2n = log2(n) + 2;
        sp.resize(lg2n, vector<int>(n));
        for (int i = 0; i < n; ++i) sp[0][i] = a[i];
        for (int i = 1; i < lg2n; ++i) {
            for (int j = 0; j < n; ++j) {
                int t = min(n - 1, j + (1 << (i - 1)));
                sp[i][j] = min(sp[i - 1][j], sp[i - 1][t]);
            }
        }
    }

    int gt(int l, int r) {
        if (l > r) swap(l, r);
        ++r;
        int t = log2(r - l);
        return min(sp[t][l], sp[t][r - (1 << t)]);
    }
};

struct LCA {
    vector<int> ord;
    vector<int> backord, h;
    SparseTable lol;

    vector<vector<int>> gr;

    void dfs(int v, int pp) {
        backord[v] = ord.size();
        ord.push_back(h[v]);
        for (auto e : gr[v]) {
            if (e == pp) continue;
            h[e] = h[v] + 1;
            dfs(e, v);
            ord.push_back(h[v]);
        }
    }

    LCA(vector<vector<int>> gr) : gr(gr) {
        int n = gr.size();
        backord.resize(n);
        h.resize(n);
        dfs(0, -1);
        lol.build(ord);
    }

    int get(int a, int b) {
        return h[a] + h[b] - 2 * lol.gt(backord[a], backord[b]);
    }
};

void solve() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; ++i) cin >> p[i];
    vector<vector<int>> gr(n);
    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        gr[a].push_back(b);
        gr[b].push_back(a);
    }
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {return p[i] < p[j];});
    vector<set<int>> lol(n);
    for (int i = 0; i < n; ++i) {
        for (auto e : gr[i]) {
            if (p[e] > p[i]) {
                lol[i].insert(p[e]);
            }
        }
    }
    DSU b(lol, n);
    LCA kek(gr);
    vector<int> dp(n + 1);
    vector<int> fr(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int v = ord[i];
        for (auto e : gr[v]) {
            if (p[e] < p[v]) {
                b.unite(v, e);
            }
        }
        int u = ord[b.ans(v, p[v]) - 1];
        fr[i + 1] = p[u];
        // cout << fr[i] << endl;
        // dp[i + 1] = dp[p[u]] + kek.get(v, u);
    }
    for (int i = n - 1; i >= 1; --i) {
        dp[i] = dp[fr[i]] + kek.get(ord[i - 1], ord[fr[i] - 1]);
    }
    cout << *max_element(dp.begin(), dp.end()) << '\n';
}

signed main() {
    int tc = 1;
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
#endif
    // cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t  << ": ";
        solve();
    }
}

• 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