Submission #1258685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258685		biank	Tree (IOI24_tree)	C++20	31 / 100	2095 ms	31792 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
 
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
 
#define pb push_back
#define eb emplace_back
 
#define fst first
#define snd second
 
using namespace std;
 
using vi = vector<int>;
using ii = pair<int, int>;
using ll = long long;

const int INF = 1e9 + 20;

template<typename T, T (*op)(const T&, const T&), T (*id)()>
struct SegTree {
    int n;
    vector<T> st;
    SegTree(int _n = 0) : n(_n), st(2 * n, id()) {};
    void init(vector<T> v) {
        assert(sz(v) == n);
        forn(i, n) st[i + n] = v[i];
        dforsn(i, 1, n) st[i] = op(st[2 * i], st[2 * i + 1]);
    }
    T query(int l, int r) {
        T lans = id(), rans = id();
        for (l += n, r += n; l < r; l /= 2, r /= 2) {
            if (l & 1) lans = op(lans, st[l++]);
            if (r & 1) rans = op(st[--r], rans);
        }
        return op(lans, rans);
    }
    void updateSet(int p, T v) {
        st[p += n] = v;
        while (p /= 2) st[p] = op(st[2 * p], st[2 * p + 1]);
    }
    void updateAdd(int p, T v) {
        p += n;
        st[p] = op(st[p], v);
        while (p /= 2) st[p] = op(st[2 * p], st[2 * p + 1]);
    }
};

const int MAX_N = 2e5 + 9;

int in[MAX_N], out[MAX_N];
int w[MAX_N], t;
vi adj[MAX_N];
int n;
bool only0and1;

void dfs(int u) {
    in[u] = t++;
    for (int v : adj[u]) dfs(v);
    out[u] = t;
}

vi trees;
vi pref;

int dfs2(int u) {
    if (w[u] == 0 || adj[u].empty()) {
        for (int v : adj[u]) trees.pb(dfs2(v));
        return w[u];
    }
    int leafs = 0;
    for (int v : adj[u]) leafs += dfs2(v);
    return leafs;
}

void init(vi P, vi W) {
    n = sz(P);
    forsn(i, 1, n) adj[P[i]].pb(i);
    only0and1 = true;
    forn(i, n) w[i] = W[i], only0and1 &= W[i] <= 1;
    t = 0;
    dfs(0);
    trees.pb(dfs2(0));
    sort(all(trees));
    pref.resize(sz(trees) + 1);
    pref[0] = 0;
    forn(i, sz(trees)) pref[i + 1] = pref[i] + trees[i];
}

ii minOp(const ii &a, const ii &b) { return min(a, b); }
ii minNeutr() { return ii{INF, INF}; }
template<typename T> T sumOp(const T &a, const T &b) { return a + b; }
template<typename T> T sumNeutr() { return 0; }

ll query(int L, int R) {
    if (only0and1) {
        int lo = -1, hi = sz(trees);
        while (hi - lo > 1) {
            int mid = (lo + hi) / 2;
            if (trees[mid] * L - R > 0) hi = mid;
            else lo = mid;
        }
        return 1LL * pref.back() * L + 1LL * (pref.back() - pref[hi]) * L - 1LL * (sz(trees) - hi) * R;
    }
    SegTree<ii, minOp, minNeutr> mini(n);
    vector<ii> a(n);
    forn(u, n) a[in[u]] = {w[u], u};
    mini.init(a);
    SegTree<ll, sumOp, sumNeutr> sum(n); 
    SegTree<int, sumOp, sumNeutr> cnt(n + 1);
    ll ret = 0LL;
    dforn(u, n) {
        if (adj[u].empty()) {
            sum.updateAdd(in[u], L);
            mini.updateSet(in[u], minNeutr());
            ret += 1LL * w[u] * L;
            continue;
        }
        ll currSum = sum.query(in[u], out[u]);
        while (currSum > R) {
            auto [_, v] = mini.query(in[u], out[u]);
            if (cnt.query(0, in[v] + 1) > 0) {
                mini.updateSet(in[v], minNeutr());
                continue;
            }
            ll sumV = sum.query(in[v], out[v]);
            ll need = min(currSum - R, sumV - L);
            currSum -= need;
            sum.updateAdd(in[v], -need);
            ret += 1LL * w[v] * need;
            if (sumV - need == L) {
                cnt.updateAdd(in[v], +1);
                cnt.updateAdd(out[v], -1);
            }
        }
    }
    return ret;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 13 / 13
• Subtask 3: 18 / 18
• Subtask 4: 0 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19