Submission #1237841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237841		Pajaraja	Tree (IOI24_tree)	C++20	41 / 100	108 ms	63788 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>
#define MAXN 200007
#define INF 1000000000000LL
using namespace std;
int n;
long long  initialValue = 0;
vector<int> p, w;
set<pair<long long, long long>> st[MAXN];
vector<int> g[MAXN];
vector<pair<long , long>> event;
vector<long long> v, val, skew;
void dfs(int s) {
    if(g[s].size() == 0) {
        initialValue += w[s];
        return;
    }
    int largestSon = 0;
    for(int i = 0; i < g[s].size(); i++) {
        dfs(g[s][i]);
        if(st[g[s][i]].size() > st[g[s][largestSon]].size()) {
            largestSon = i;
        }
    }
    initialValue += (g[s].size() - 1) * w[s];
    long long len = g[s].size() - 1;
    long long koef = -w[s];
    for(int i = 0; i < g[s].size(); i++) {
        int u = g[s][i];
        vector<pair<long long, long long>> removal;
        long long total = 1;
        for(auto it: st[u]) {
            if(koef < it.first) break;
            event.push_back({total, it.first - koef});
            total += it.second;
            event.push_back({total, koef - it.first});
            len += it.second;
            removal.push_back(it);
        }
        for(auto it: removal) st[u].erase(it);
    }
    swap(st[s], st[g[s][largestSon]]);
    for(int i = 0; i < g[s].size(); i++) if(i != largestSon) {
        for(auto it: st[g[s][i]]) st[s].insert(it);
        st[g[s][i]].clear();
    }
    st[s].insert({koef, len});
}
void init(std::vector<int> P, std::vector<int> W) {
    p = P;
    w = W;
    n = (int)p.size();
    g[n].push_back(0);
    w.push_back(0);
    for(int i = 1; i < n; i++) {
        g[P[i]].push_back(i);
    }
    dfs(n);
    sort(event.begin(), event.end());
    long long total = initialValue;
    long long curCoef = 0;
    long long lastPos = event[0].first;
    for(int i = 0; i < event.size(); i++) {
        total += curCoef * (event[i].first - lastPos);
        lastPos = event[i].first;
        curCoef += event[i].second;
        v.push_back(lastPos);
        skew.push_back(curCoef);
        val.push_back(total);
    }
}
long long query(int L, int R) {
    if(n == 1) return L;
    int l = 0, r = v.size() - 1;
    while(l != r) {
        int s = (l + r + 1) / 2;
        if(v[s] * L <= R) l = s;
        else r = s - 1;
    }
    return val[l] * L + skew[l] * (R - v[l] * L);
}

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