| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 926579 | adhityamv | Road Closures (APIO21_roads) | C++17 | 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;
#define int long long
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define setit _Rb_tree_const_iterator<long long>
const int INF=1000000000;
const int K=200000;
int seg[4*K]={};
int lazy[4*K]={};
void Build(int l,int r,int pos){
if(l==r){
seg[pos]=0;
lazy[pos]=INF;
return;
}
int m=(l+r)/2;
Build(l,m,2*pos);
Build(m+1,r,2*pos+1);
seg[pos]=seg[2*pos]+seg[2*pos+1];
lazy[pos]=INF;
}
void UpdateLazy(int l,int r,int pos){
if(lazy[pos]==INF) return;
seg[pos]=(r-l+1LL)*lazy[pos];
if(l!=r){
lazy[2*pos]=lazy[pos];
lazy[2*pos+1]=lazy[pos];
}
lazy[pos]=INF;
}
void Update(int l,int r,int pos,int ql,int qr,int qval){
if(ql>qr) return;
UpdateLazy(l,r,pos);
if(ql>r || qr<l) return;
if(ql<=l && qr>=r){
lazy[pos]=qval;
UpdateLazy(l,r,pos);
return;
}
int m=(l+r)/2;
Update(l,m,2*pos,ql,qr,qval);
Update(m+1,r,2*pos+1,ql,qr,qval);
seg[pos]=(seg[2*pos]+seg[2*pos+1]);
}
int Query(int l,int r,int pos, int ql,int qr){
if(ql>qr) return 0;
UpdateLazy(l,r,pos);
if(ql>r || qr<l) return 0;
if(ql<=l && qr>=r){
return seg[pos];
}
int m=(l+r)/2;
return (Query(l,m,2*pos,ql,qr)+Query(m+1,r,2*pos+1,ql,qr));
}
const int N=100000;
vector<pii> edges[N];
vector<int> et;
int n,m;
int deg[N];
int depth[N];
int focc[N];
int locc[N];
int parent[N];
int upweight[N];
void euler_tour(int u,int p){
parent[u]=p;
focc[u]=et.size();
et.push_back(u);
for(auto v:edges[u]){
if(v.fi==p) continue;
depth[v.fi]=depth[u]+1;
upweight[v.fi]=v.se;
euler_tour(v.fi,u);
et.push_back(u);
}
locc[u]=et.size()-1;
}
vector<int> bydeg[N];
multiset<int> allnums[N];
multiset<int> topk[N];
multiset<int> topk1[N];
int dp[N];
int dp1[N];
void dfs(int u,int p){
dp[u]=dp1[u]=0;
for(auto v:edges[u]){
if(v.fi==p) continue;
dfs(v.fi,u);
allnums[u].insert(upweight[v.fi]+dp1[v.fi]-dp[v.fi]);
dp[u]+=dp[v.fi];
dp1[u]+=dp[v.fi];
}
auto it=allnums[u].end();
if(it!=allnums[u].begin()){
it--;
topk[u].insert(*it);
dp[u]+=max(*it,0LL);
allnums[u].erase(it);
}
}
int k=2;
void updatepp(){
vector<pii> needupdate;
for(int i:bydeg[k]) needupdate.push_back(mp(depth[i],i));
for(int i:bydeg[k]){
if(i==0) continue;
if(deg[parent[i]]>=k) continue;
needupdate.push_back(mp(depth[parent[i]],parent[i]));
}
sort(needupdate.begin(),needupdate.end(),greater<pii>());
for(auto pa:needupdate){
int u=pa.se;
int orval=dp[u];
int orval1=dp1[u];
if(topk1[u].size()!=topk[u].size()){
dp1[u]+=max(*topk[u].begin(),0LL);
topk1[u].insert(*topk[u].begin());
}
if(!allnums[u].empty()){
auto it=allnums[u].end();
it--;
dp[u]+=max(*it,0LL);
topk[u].insert(*it);
allnums[u].erase(it);
}
int ex=Query(0,m-1,1,focc[u],locc[u]);
dp[u]+=ex;
dp1[u]+=ex;
if(u==0) continue;
if(deg[u]<k){
Update(0,m-1,1,focc[u],locc[u],0);
Update(0,m-1,1,focc[u],focc[u],dp[u]-orval);
} else{
int p=parent[u];
int val=upweight[u]+orval1-orval;
bool w=false;
bool w1=false;
if(topk1[p].find(val)!=topk1[p].end()){
topk[p].erase(topk[p].find(val));
topk1[p].erase(topk1[p].find(val));
dp[p]-=max(val,0LL);
dp1[p]-=max(val,0LL);
} else if(topk[p].find(val)!=topk[p].end()){
topk[p].erase(topk[p].find(val));
dp[p]-=max(val,0LL);
} else{
allnums[p].erase(allnums[p].find(val));
}
val=upweight[u]+dp1[u]-dp[u];
topk[p].insert(val);
dp[p]+=max(val,0LL);
topk1[p].insert(val);
dp1[p]+=max(val,0LL);
if(topk[p].size()>=k){
auto it=topk[p].begin();
allnums[p].insert(*it);
dp[p]-=max(*it,0LL);
topk[p].erase(it);
}
if(topk1[p].size()>=k-1){
dp1[p]-=max(*topk1[p].begin(),0LL);
topk1[p].erase(topk1[p].begin());
}
}
}
Update(0,m-1,1,0,n-1,0);
k++;
}
vector<int> minimum_closure_costs(int nn,vector<int> u,vector<int> v,vector<int> w){
n=nn;
int tot=0;
for(int i=0;i<n-1;i++){
edges[u[i]].push_back(mp(v[i],w[i]));
edges[v[i]].push_back(mp(u[i],w[i]));
deg[u[i]]++,deg[v[i]]++;
tot+=w[i];
}
depth[0]=0;
euler_tour(0,-1);
m=et.size();
vector<int> ans;
ans.push_back(tot);
dfs(0,-1);
ans.push_back(tot-dp[0]);
for(int i=0;i<n;i++){
for(int j=0;j<=deg[i];j++) bydeg[j].push_back(i);
}
Build(0,m-1,1);
while(k<n){
updatepp();
ans.push_back(tot-dp[0]);
}
return ans;
}