Submission #164512

#	Time	Username	Problem	Language	Result	Execution time	Memory
164512		HungAnhGoldIBO2020	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	1074 ms	59000 KiB

designated_cities

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+2;
const int inf=1e16+2;
int n,ans[N],dis[N],idx=0,idx1=0;
vector<pair<pair<int,int>,int> > adj[N];
int it_max[4*N],lazy[4*N],tin[N],tout[N],now=0,par[N],sum1=0,wei[N],pos[N];
bool used[N];
void build(int idx,int l,int r){
	lazy[idx]=0;
	if(l==r){
		it_max[idx]=dis[pos[l]];
		return;
	}
	build(2*idx,l,(l+r)/2);
	build(2*idx+1,(l+r)/2+1,r);
	it_max[idx]=max(it_max[2*idx],it_max[2*idx+1]);
}
void push(int idx,int l,int r){
	if(l<r){
		it_max[2*idx]+=lazy[idx];
		it_max[2*idx+1]+=lazy[idx];
		lazy[2*idx]+=lazy[idx];
		lazy[2*idx+1]+=lazy[idx];
	}
	lazy[idx]=0;
	return;
}
void add(int idx,int l,int r,int lef,int rig,int val){
	if(lef>rig){
		return;
	}
	if(l>rig||r<lef){
		return;
	}
	if(l>=lef&&r<=rig){
		it_max[idx]+=val;
		lazy[idx]+=val;
		return;
	}
	push(idx,l,r);
	add(2*idx,l,(l+r)/2,lef,rig,val);
	add(2*idx+1,(l+r)/2+1,r,lef,rig,val);
	it_max[idx]=max(it_max[2*idx],it_max[2*idx+1]);
}
int trace(int idx,int l,int r){
	if(l==r){
		return pos[l];
	}
	push(idx,l,r);
	if(it_max[2*idx]==it_max[idx]){
		return trace(2*idx,l,(l+r)/2);
	}
	assert(it_max[2*idx+1]==it_max[idx]);
	return trace(2*idx+1,(l+r)/2+1,r);
}
void dfs1(int x,int p){
	now++;
	tin[x]=now;
	pos[now]=x;
	for(auto i:adj[x]){
		if(i.first.first!=p){
			dis[i.first.first]=dis[x]+i.first.second;
			dfs1(i.first.first,x);
			sum1+=i.first.second;
		}
	}
	tout[x]=now;
}
void dfs(int x,int p){
	ans[1]=min(ans[1],sum1);
	if(ans[2]>sum1-it_max[1]){
		ans[2]=sum1-it_max[1];
		idx=x;
		idx1=trace(1,1,n);
	}
	for(auto i:adj[x]){
		if(i.first.first!=p){
			sum1-=i.first.second;
			sum1+=i.second;
			add(1,1,n,tin[i.first.first],tout[i.first.first],-i.first.second);
			add(1,1,n,1,tin[i.first.first]-1,i.second);
			add(1,1,n,tout[i.first.first]+1,n,i.second);
			dfs(i.first.first,x);
			add(1,1,n,tin[i.first.first],tout[i.first.first],i.first.second);
			add(1,1,n,1,tin[i.first.first]-1,-i.second);
			add(1,1,n,tout[i.first.first]+1,n,-i.second);
			sum1+=i.first.second;
			sum1-=i.second;
		}
	}
}
void dfs2(int x,int p){
	now++;
	tin[x]=now;
	pos[now]=x;
	for(auto i:adj[x]){
		if(i.first.first!=p){
			par[i.first.first]=x;
			dis[i.first.first]=dis[x]+i.first.second;
			sum1+=i.first.second;
			wei[i.first.first]=i.first.second;
			dfs2(i.first.first,x);
		}
	}
	tout[x]=now;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int i,j,k,l,q,m;
	cin>>n;
	for(i=1;i<n;i++){
		cin>>j>>k>>l>>m;
		adj[j].push_back({{k,l},m});
		adj[k].push_back({{j,m},l});
		ans[i]=inf;
	}
	ans[n]=inf;
	dfs1(1,1);
	build(1,1,n);
	dfs(1,1);
	dis[idx]=sum1=now=0;
	dfs2(idx,idx);
	build(1,1,n);
	used[idx]=true;
	for(i=2;i<=n;i++){
		ans[i]=sum1-it_max[1];
		sum1-=it_max[1];
		j=trace(1,1,n);
		while(!used[j]){
			used[j]=true;
			add(1,1,n,tin[j],tout[j],-wei[j]);
			j=par[j];
		}
	}
	cin>>q;
	for(i=1;i<=q;i++){
		cin>>j;
		cout<<ans[j]<<'\n';
	}
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44