| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 961868 | socpite | Road Closures (APIO21_roads) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+5;
const long long INF = 1e18;
vector<pair<int, long long>> g[maxn];
vector<long long> dp[2][maxn];
long long tdp[2][maxn];
int pos[maxn];
struct Fenwick{
vector<int> cnt;
vector<long long> sum;
int sz;
Fenwick(int _sz): sz(_sz){
cnt.assign(sz + 1, 0);
sum.assign(sz + 1, 0);
}
void add(int idx, long long val){
assert(idx);
for(idx; idx <= sz; idx += idx&(-idx)){
cnt[idx]++;
sum[idx] += val;
}
}
pair<int, long long> query(int k){
int pos = 0;
long long re = 0;
for(int i = 17; i >= 0; i--){
if((pos^(1<<i)) > sz)continue;
if(cnt[pos^(1<<i)] <= k){
pos^=(1<<i);
k -= cnt[pos];
re += sum[pos];
}
}
if(k > 0)return {pos, INF};
return {pos, re};
}
};
void dfs(int x, int p, long long pe){
vector<pair<int, int>> child_d;
vector<pair<long long, int>> child_w = {{pe, p}};
for(auto v: g[x]){
if(v.first == p)continue;
dfs(v.first, x, v.second);
child_d.push_back({g[v.first].size(), v.first});
child_w.push_back({v.second, v.first});
}
sort(child_w.begin(), child_w.end());
sort(child_d.begin(), child_d.end());
Fenwick fw(child_w.size());
for(int i = 0; i < child_w.size(); i++){
pos[child_w[i].second] = i+1;
}
fw.add(pos[p], pe);
int ptr = 0;
for(int i = 0; i < g[x].size(); i++){
tdp[0][i] = tdp[1][i] = INF;
while(ptr < child_d.size() && child_d[ptr].first == i){
int id = child_d[ptr].second;
fw.add(pos[id], child_w[pos[id] - 1].first);
ptr++;
}
long long sum = 0;
vector<long long> save_cost;
for(int j = ptr; j < child_d.size(); j++)save_cost.push_back(dp[1][child_d[j].second][i] - dp[0][child_d[j].second][i]);
sort(save_cost.begin(), save_cost.end());
for(int j = 0; j <= save_cost.size(); j++){
auto cost = fw.query(int(g[x].size()) - i - j);
cost.second += sum;
tdp[0][i] = min(tdp[0][i], cost.second);
if(cost.first < pos[p]){
tdp[1][i] = min(tdp[1][i], fw.query(int(g[x].size()) - i - j - 1).second + pe);
}
else tdp[1][i] = min(tdp[1][i], cost.second);
if(j < save_cost.size())sum += save_cost[j];
}
}
for(auto v: g[x]){
if(v.first == p)continue;
if(dp[0][v.first].size() > dp[0][x].size())dp[0][x].swap(dp[0][v.first]);
for(int i = 0; i < dp[0][v.first].size(); i++)dp[0][x][i] += dp[0][v.first][i];
}
dp[1][x].resize(g[x].size());
while(dp[0][x].size() < g[x].size())dp[0][x].push_back(0);
for(int i = 0; i < g[x].size(); i++){
dp[1][x][i] = dp[0][x][i];
for(int j = 0; j < 2; j++)dp[j][x][i] += tdp[j][i];
}
//
}
vector<long long> minimum_closure_cost(int N, vector<int> U, vector<int> V, vector<int> W){
vector<long long> re(N, 0);
for(int i = 0; i < N - 1; i++){
g[U[i]].push_back({V[i], W[i]});
g[V[i]].push_back({U[i], W[i]});
}
dfs(1, 0, INF);
for(int i = 0; i < dp[0][1].size(); i++){
re[i] = dp[0][1][i];
}
return re;
}