Submission #1189204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189204		patgra	Cat Exercise (JOI23_ho_t4)	C++20	41 / 100	338 ms	82552 KiB

Main

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

int n, tb, maxLog;
vector<int> perm;
vector<pair<int, int>> t;
vector<int> lz;
vector<vector<int>> g;
vector<int> depth, subsz, preord;
int pre_t;
ll ans, curAns;
vector<vector<int>> stMin;
vector<int> euDep, firstInEu;

void tAdd(int l, int r, int x) {
    DC << "   tAdd(" << l << ' ' << r << ' ' << x << ")" << eol;
    l += tb; r += tb;
    t[l].first += x;
    if(r != l) t[r].first += x;
    while(l / 2 != r / 2) {
        if(l % 2 == 0) t[l + 1].first += x, lz[l + 1] += x;
        if(r % 2 == 1) t[r - 1].first += x, lz[r - 1] += x;
        l /= 2;
        r /= 2;
        t[l] = max(t[2 * l], t[2 * l + 1]);
        t[l].first += lz[l];
        t[r] = max(t[2 * r], t[2 * r + 1]);
        t[r].first += lz[r];
    }
    l /= 2;
    while(l) t[l] = max(t[2 * l], t[2 * l + 1]), t[l].first += lz[l], l /= 2;
}

void dfs(int v, int p) {
    depth[v] = depth[p] + 1;
    subsz[v] = 1;
    preord[v] = pre_t++;
    firstInEu[v] = (int)euDep.size();
    euDep.pb(depth[v]);
    repIn(u, g[v]) if(u != p) dfs(u, v), euDep.pb(depth[v]), subsz[v] += subsz[u];
}

int stMinQ(int l, int r) {
    if(l > r) swap(l, r);
    int k = 31 - __builtin_clz(r - l + 1);
    return min(stMin[l][k], stMin[r - (1 << k) + 1][k]);
}

int dist(int a, int b) {
    return depth[a] + depth[b] - 2 * stMinQ(firstInEu[a], firstInEu[b]);
}

void reku(int v, int anc) {
    if(anc) curAns += dist(v, anc);
    DC << " ->  (" << v << ' ' << anc << ")  ans " << curAns << eol;
    ans = max(ans, curAns);
    repIn(u, g[v]) {
        if(depth[u] < depth[v]) {
            tAdd(preord[v], preord[v] + subsz[v] - 1, -1);
            if(t[1].first == 0) reku(t[1].second, v);
            tAdd(preord[v], preord[v] + subsz[v] - 1, 1);
        }
        else {
            tAdd(0, n - 1, -1);
            tAdd(preord[u], preord[u] + subsz[u] - 1, 1);
            if(t[1].first == 0) reku(t[1].second, v);
            tAdd(0, n - 1, 1);
            tAdd(preord[u], preord[u] + subsz[u] - 1, -1);
        }
    }
    if(anc) curAns -= dist(v, anc);
    DC << " <-  (" << v << ' ' << anc << ")" << eol;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    perm.resize(n + 1);
    depth.resize(n + 1);
    subsz.resize(n + 1);
    preord.resize(n + 1);
    firstInEu.resize(n + 1);
    g.resize(n + 1);
    tb = 1 << (32 - __builtin_clz(n - 1));
    t.resize(2 * tb);
    lz.resize(2 * tb);
    rep(i, 0, n) cin >> perm[i + 1];
    rep(i, 1, n) {
        int a, b;
        cin >> a >> b;
        a = perm[a], b = perm[b];
        DC << a << ' ' << b << eol;
        g[a].pb(b);
        g[b].pb(a);
    }

    dfs(n, 0);
    rep(i, 1, n + 1) t[preord[i] + tb].second = i;
    rep(i, n, tb) t[i + tb].first = -1;
    repD(i, tb - 1, 0) t[i] = max(t[2 * i], t[2 * i + 1]);

    maxLog = 32 - __builtin_clz(n + 1);
    stMin.resize(euDep.size(), vector<int>(maxLog, 1e9));
    rep(i, 0, (int)euDep.size()) stMin[i][0] = euDep[i];
    rep(k, 1, maxLog) rep(i, 0, (int)stMin.size()) stMin[i][k] = min(stMin[i][k - 1], stMin[min((int)stMin.size() - 1, i + (1 << (k - 1)))][k - 1]);

    reku(n, 0);
    cout << ans << '\n';
}

• 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