Submission #924742

#	Time	Username	Problem	Language	Result	Execution time	Memory
924742		winter0101	Road Closures (APIO21_roads)	C++14	100 / 100	198 ms	104524 KiB

roads

#include<bits/stdc++.h>
#include "roads.h"
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=2e5+5e4+9;
long long bonus[maxn];
vector<int>vertice[maxn],edg[maxn],nw[maxn];
int deg[maxn];
vector<pii>a[maxn];
int in[maxn],tme=0,rev[maxn];
struct IT{
vector<long long>st;
vector<int>cnt;
void resz(int n){
st.resize(4*n+9);
cnt.resize(4*n+9);
}
void update(int id,int l,int r,int u,long long val){
if (l>u||r<u)return;
if (l==r){
    st[id]+=val;
    cnt[id]++;
    return;
}
int mid=(l+r)>>1;
update(id<<1,l,mid,u,val);
update(id<<1|1,mid+1,r,u,val);
st[id]=st[id<<1]+st[id<<1|1];
cnt[id]=cnt[id<<1]+cnt[id<<1|1];
}
long long kth(int id,int l,int r,int v){
if (v<0)return 0;
if (cnt[id]<=v)return st[id];
if (l==r)return 0;
int mid=(l+r)>>1;
if (cnt[id<<1]<v)return st[id<<1]+kth(id<<1|1,mid+1,r,v-cnt[id<<1]);
return kth(id<<1,l,mid,v);
}
}st[maxn];
int nn[maxn];
struct event{
int u,id;
long long val;
};
vector<event>upd[maxn];
void dfs(int u,int par){
in[u]=++tme;
rev[tme]=u;
for (auto v:a[u]){
nn[u]++;
if (v.fi==par)continue;
dfs(v.fi,u);
}
st[u].resz(nn[u]);
sort(all(a[u]),[](const pii &p,const pii &q){
return p.se>q.se;
});
int id=0;
for (auto v:a[u]){
id++;
if (deg[v.fi]<deg[u])upd[min(deg[v.fi],deg[u])].pb({u,id,v.se});
}
}
long long f[maxn],g[maxn];
bool vis[maxn];
void redfs(int u,int mindeg){
f[u]=g[u]=0;
vis[u]=1;
priority_queue<long long>t;
for (auto v:a[u]){
if (vis[v.fi])continue;
redfs(v.fi,mindeg);
f[u]+=f[v.fi];
g[u]+=f[v.fi];
if (f[v.fi]<g[v.fi]+v.se){
t.push(g[v.fi]+v.se-f[v.fi]);
}
}
long long x=st[u].kth(1,1,nn[u],mindeg),y=st[u].kth(1,1,nn[u],mindeg-1);
long long n1=0,n2=0;
for1(i,1,mindeg){
if (t.empty())break;
n1+=t.top();
if (i<mindeg)n2+=t.top();
t.pop();
x=max(x,n1+st[u].kth(1,1,nn[u],mindeg-i));
if (i<mindeg)y=max(y,n2+st[u].kth(1,1,nn[u],mindeg-1-i));
}
f[u]+=x,g[u]+=y;
}
std::vector<long long> minimum_closure_costs(int N, std::vector<int>U,std::vector<int> V,std::vector<int> W) {
int n=N;
long long all=0;
for1(i,0,n-2)U[i]++,V[i]++,all+=W[i];
for1(i,0,n-2)deg[U[i]]++,deg[V[i]]++;
for1(i,1,n)vertice[deg[i]].pb(i);
for1(i,0,n-2){
bonus[max(deg[U[i]],deg[V[i]])]+=W[i];
a[U[i]].pb({V[i],W[i]});
a[V[i]].pb({U[i],W[i]});
}
dfs(1,0);
set<int>tin;
for1(i,1,n)tin.insert(i);
for1(i,0,n-2){
for1(j,1,min(deg[U[i]],deg[V[i]])-1)edg[j].pb(i);
}
long long dd=0;
vector<long long>cost(n);
cost[0]=all;
for1(i,1,n-1){
for (auto v:tin)a[rev[v]].clear(),vis[rev[v]]=0;
dd+=bonus[i];
long long sum=0;
for (auto v:vertice[i])tin.erase(in[v]);
for (auto v:edg[i]){
a[U[v]].pb({V[v],W[v]});
a[V[v]].pb({U[v],W[v]});
}
for (auto v:upd[i]){
if (deg[v.u]>i)st[v.u].update(1,1,nn[v.u],v.id,v.val);
}
for (auto v:tin){
if (!vis[rev[v]]){
redfs(rev[v],i);
sum+=f[rev[v]];
}
}
cost[i]=all-sum-dd;
}
return cost;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 17 / 17
• Subtask 6: 25 / 25
• Subtask 7: 22 / 22