#include "roads.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define ar array
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int inf = 2e9;
struct node{
ll x, y, cnt, cc, sum;
node *lx, *rx;
node(int v) : x(v), cnt(1), cc(1), sum(v), lx(NULL), rx(NULL){
y = uniform_int_distribution<int>(0, inf)(rng);
}
};
struct RBST{
void upd(node* a){
a->cnt = a->cc, a->sum = a->x * a->cc;
if(a->lx != NULL) a->cnt += a->lx->cnt, a->sum += a->lx->sum;
if(a->rx != NULL) a->cnt += a->rx->cnt, a->sum += a->rx->sum;
}
node* merge(node* a, node* b){
if(a == NULL) return b;
if(b == NULL) return a;
if(a->y > b->y){
a->rx = merge(a->rx, b);
upd(a);
return a;
} else {
b->lx = merge(a, b->lx);
upd(b);
return b;
}
}
ar<node*, 2> split(node* a, int v){
if(a == NULL) return {NULL, NULL};
if(v <= a->x){
auto tt = split(a->lx, v);
a->lx = tt[1];
upd(a);
return {tt[0], a};
} else {
auto tt = split(a->rx, v);
a->rx = tt[0];
upd(a);
return {a, tt[1]};
}
}
bool check(node*& root, int v){
if(root == NULL) return false;
if(root->x == v){
root->cc++;
upd(root);
return true;
} if(root->x < v) return check(root->lx, v);
else return check(root->rx, v);
}
bool rcheck(node*& root, int v){
if(root == NULL) return false;
if(root->x == v){
assert(root->cc > 0);
root->cc--, upd(root);
return true;
} if(root->x < v) return rcheck(root->lx, v);
else return rcheck(root->rx, v);
}
void insert(node*& root, int v){
if(check(root, v)) return;
node* tmp = new node(v);
auto tt = split(root, v);
root = merge(tt[0], merge(tmp, tt[1]));
}
void erase(node*& root, int v){
assert(rcheck(root, v));
//~ auto L = split(root, v);
//~ auto R = split(L[1], v + 1);
//~ assert(R[0] != NULL);
//~ if(R[0] == NULL){
//~ root = merge(L[0], R[1]);
//~ return;
//~ }
//~ if(--R[0]->cc){
//~ upd(R[0]);
//~ root = merge(L[0], merge(R[0], R[1]));
//~ } else {
//~ root = merge(L[0], R[1]);
//~ }
}
ll get(node* a, int v){
if(v == 0 || a == NULL) return 0;
if(a->lx != NULL && v < a->lx->cnt) return get(a->lx, v);
ll res = 0;
if(a->lx != NULL) res += a->lx->sum, v -= a->lx->cnt;
if(v <= a->cc) return res + v * a->x;
res += a->cc * a->x, v -= a->cc;
return res + get(a->rx, v);
}
}tree;
const int N = 1e5 + 5;
vector<int> edges[N];
vector<ar<ll, 2>> work[N];
int d[N], used[N], CUR;
ll dp[N][2], tot[N];
node* bad[N];
multiset<int> mm[N];
void dfs(int u, int p = -1){
used[u] = 1;
dp[u][0] = dp[u][1] = tot[u];
vector<ll> tt;
for(auto x : work[u]){
if(x[0] == p) continue;
tot[x[0]] -= x[1];
dfs(x[0], u);
tot[x[0]] += x[1];
dp[u][0] += dp[x[0]][0], dp[u][1] += dp[x[0]][0];
tt.push_back(dp[x[0]][1] - dp[x[0]][0] - x[1]);
}
sort(tt.begin(), tt.end());
for(int t=0;t<2;t++){
ll cur = dp[u][t];
for(int j=0;j<=min((int)tt.size(), CUR - t);j++){
int rem = CUR - t - j;
dp[u][t] = min(dp[u][t], cur + tree.get(bad[u], rem));
if(j < (int)tt.size()) cur += tt[j];
}
}
}
vector<ll> minimum_closure_costs(int n, vector<int> u, vector<int> v, vector<int> w) {
vector<int> p;
p.push_back(n - 1);
for(int i=0;i<n-1;i++){
d[u[i]]++, d[v[i]]++;
edges[u[i]].push_back(i);
edges[v[i]].push_back(i);
tree.insert(bad[u[i]], -w[i]);
tree.insert(bad[v[i]], -w[i]);
mm[v[i]].insert(-w[i]), mm[u[i]].insert(-w[i]);
tot[v[i]] += w[i], tot[u[i]] += w[i];
p.push_back(i);
}
sort(p.begin(), p.end(), [&](int i, int j){
return (d[i] > d[j]);
});
vector<ll> tt, res(n);
auto add = [&](int a){
tt.push_back(a);
for(auto i : edges[a]){
int x = u[i] ^ v[i] ^ a;
tree.erase(bad[x], -w[i]);
assert(mm[x].count(-w[i]));
mm[x].erase(mm[x].find(-w[i]));
work[x].push_back({a, w[i]});
}
};
int j = 0;
for(int x=n-1;~x;x--){ CUR = x;
while(j < n && d[p[j]] >= x){
add(p[j]);
j++;
}
for(auto u : tt){
if(used[u]) continue;
dfs(u);
res[x] += dp[u][0];
}
for(auto x : tt) used[x] = 0;
}
return res;
}
/*
5
0 1 1
0 2 4
0 3 3
2 4 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
2 0 0 0 0
2 2 0 0 0
0 0 0 0 0
0 0 0 0 0
10 5 1 0 0
10 8 4 1 0
*/
Compilation message
jumps.cpp:1:10: fatal error: roads.h: No such file or directory
1 | #include "roads.h"
| ^~~~~~~~~
compilation terminated.
