| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1237845 | Pajaraja | 트리 (IOI24_tree) | C++20 | 0 ms | 0 KiB |
#include "tree.h"
#include <bits/stdc++.h>
#define MAXN 200007
using namespace std;
int n;
long long initialValue = 0;
vector<int> p;
set<pair<long long, long long>> st[MAXN];
vector<int> g[MAXN];
vector<pair<long long, long long>> event;
vector<long long> w, 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() - 1LL) * 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);
}