Submission #1302073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302073		regulardude6	Tree (IOI24_tree)	C++20	7 / 100	83 ms	34244 KiB

tree

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

using ll = long long;

struct DSU {
    vector<int> p, sz;
    vector<int> leaves;
    vector<ll> mn;
    DSU(int n): p(n), sz(n,1), leaves(n,0), mn(n,0) { iota(p.begin(), p.end(), 0); }
    int find(int x){ while(p[x]!=x){ p[x]=p[p[x]]; x=p[x]; } return x; }
    int unite(int a,int b){
        a=find(a); b=find(b);
        if(a==b) return a;
        if(sz[a]<sz[b]) swap(a,b);
        p[b]=a;
        sz[a]+=sz[b];
        leaves[a]+=leaves[b];
        mn[a]=min(mn[a], mn[b]);
        return a;
    }
};

static int N;
static vector<int> P;
static vector<ll> W;
static vector<vector<int>> ch;
static vector<char> isLeaf, active;
static ll leafSum;
static int totalLeaves;

static vector<pair<int,ll>> ev;
static vector<ll> prefD, prefKD;

void init(vector<int> _P, vector<int> _W) {
    P = _P;
    N = (int)P.size();
    W.assign(N, 0);
    for(int i=0;i<N;i++) W[i] = (ll)_W[i];

    ch.assign(N, {});
    int root = 0;
    for(int i=0;i<N;i++){
        if(P[i] == -1) root = i;
        else ch[P[i]].push_back(i);
    }

    isLeaf.assign(N, 0);
    leafSum = 0;
    totalLeaves = 0;
    for(int i=0;i<N;i++){
        if(ch[i].empty()){
            isLeaf[i] = 1;
            leafSum += W[i];
            totalLeaves++;
        }
    }

    active.assign(N, 0);
    DSU dsu(N);

    for(int i=0;i<N;i++){
        if(isLeaf[i]){
            active[i] = 1;
            dsu.leaves[i] = 1;
            dsu.mn[i] = 0;
        }
    }

    vector<int> internal;
    internal.reserve(N);
    for(int i=0;i<N;i++) if(!isLeaf[i]) internal.push_back(i);
    sort(internal.begin(), internal.end(), [&](int a,int b){
        if(W[a] != W[b]) return W[a] > W[b];
        return a < b;
    });

    ev.clear();
    ev.reserve(2LL*N);

    auto add_ev = [&](int k, ll d){
        if(k <= 0) return;
        if(d == 0) return;
        ev.push_back({k, d});
    };

    for(int v: internal){
        ll wv = W[v];
        active[v] = 1;
        dsu.leaves[v] = 0;
        dsu.mn[v] = wv;

        int r = dsu.find(v);

        add_ev(dsu.leaves[r], -dsu.mn[r]);

        vector<int> roots;
        roots.reserve(ch[v].size() + 1);

        if(P[v] != -1 && active[P[v]]) roots.push_back(dsu.find(P[v]));
        for(int u: ch[v]) if(active[u]) roots.push_back(dsu.find(u));

        sort(roots.begin(), roots.end());
        roots.erase(unique(roots.begin(), roots.end()), roots.end());

        for(int rr: roots){
            rr = dsu.find(rr);
            r = dsu.find(r);
            if(rr == r) continue;
            add_ev(dsu.leaves[rr], -dsu.mn[rr]);
            r = dsu.unite(r, rr);
        }

        r = dsu.find(v);
        dsu.mn[r] = wv;
        add_ev(dsu.leaves[r], +dsu.mn[r]);
    }

    sort(ev.begin(), ev.end(), [&](auto &a, auto &b){
        if(a.first != b.first) return a.first < b.first;
        return a.second < b.second;
    });

    int m = (int)ev.size();
    prefD.assign(m+1, 0);
    prefKD.assign(m+1, 0);
    for(int i=0;i<m;i++){
        prefD[i+1] = prefD[i] + ev[i].second;
        prefKD[i+1] = prefKD[i] + (ll)ev[i].first * ev[i].second;
    }
}

long long query(int L, int R) {
    ll LL = (ll)L, RR = (ll)R;
    ll T = (RR + LL - 1) / LL;
    if(T <= 1) T = 1;
    if(T > totalLeaves + 1) return leafSum * LL;

    int m = (int)ev.size();
    int idx = lower_bound(ev.begin(), ev.end(), make_pair((int)T, (ll)-4e18),
                          [&](const pair<int,ll>& a, const pair<int,ll>& b){
                              if(a.first != b.first) return a.first < b.first;
                              return a.second < b.second;
                          }) - ev.begin();

    ll sufD = prefD[m] - prefD[idx];
    ll sufKD = prefKD[m] - prefKD[idx];

    return leafSum * LL + sufKD * LL - sufD * RR;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 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