Submission #1258711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258711		biank	Tree (IOI24_tree)	C++20	17 / 100	129 ms	42116 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;
bool done[MAX_N];
vi adj[MAX_N];
int n;
bool only0and1;

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

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

SegTree<ii, minOp, minNeutr> mini;
SegTree<int, sumOp, sumNeutr> sum;

vector<ii> terms;
ll sumOfLeafs;
vector<ll> prefA, prefB;

void solve(int u, int delta) {
    while (true) {
        auto [minW, v] = mini.query(in[u], out[u]);
        if (minW == INF) { //leaf
            sum.updateSet(in[v], 0);
            done[v] = true;
            return;
        }
        int leafs = sum.query(in[u], out[u]);
        terms.eb(leafs, minW - delta);
        delta = minW;
        for (int c : adj[v]) {
            if (!done[c]) solve(c, delta);
        }
        sum.updateSet(in[v], 1);
        mini.updateSet(in[v], ii{INF, -1});
    }
}

void init(vi P, vi W) {
    n = sz(P);
    forsn(i, 1, n) adj[P[i]].pb(i);
    forn(i, n) w[i] = W[i];
    t = 0;
    dfs0(0);
    vector<ii> v(n);
    vi c(n);
    mini = SegTree<ii, minOp, minNeutr>(n);
    sum = SegTree<int, sumOp, sumNeutr>(n);
    forn(u, n) {
        if (out[u] - in[u] == 1) {
            v[in[u]] = {INF, u}, c[in[u]] = 1;
            sumOfLeafs += w[u];
        } else {
            v[in[u]] = {w[u], u}, c[in[u]] = 0;
        }
    }
    mini.init(v), sum.init(c);
    solve(0, 0);
    sort(all(terms));
    prefA.resize(sz(terms) + 1);
    prefB.resize(sz(terms) + 1);
    prefA[0] = 0, prefB[0] = 0;
    forn(i, sz(terms)) {
        prefA[i + 1] = prefA[i] + terms[i].fst * terms[i].snd;
        prefB[i + 1] = prefB[i] - terms[i].snd;
    }
}

ll query(int L, int R) {
    int lo = -1, hi = sz(terms);
    while (hi - lo > 1) {
        int mid = (lo + hi) / 2;
        if (1LL * terms[mid].fst * L - R > 0) hi = mid;
        else lo = mid;
    }
    return sumOfLeafs * L + (prefA.back() - prefA[hi]) * L + (prefB.back() - prefB[hi]) * R;
}

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