Submission #526904

#	Time	Username	Problem	Language	Result	Execution time	Memory
526904		wildturtle	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	1085 ms	72108 KiB

designated_cities

#include<bits/stdc++.h>
#define ll long long
#define f first
#define sc second
#define pb push_back
using namespace std;
ll a,b,c,d,i,e,f,g,n,m,k,l;
ll t,maxroot,fotlebi,wvrt,sum,idx;
pair < pair <ll,ll> , pair <ll,ll> > A[200005];
ll in[200005],out[200005],P[200005],D[200005],down[200005],inv[200005];
ll lz[800005];
pair <ll,ll> tree[800005],pr;
ll ans[200005],fix[200005];
vector < pair < ll, pair <ll,ll> > > v[200005];
void build(ll node,ll le,ll ri) {
	lz[node]=0;
	if(le==ri) {
		tree[node].f=0;
		tree[node].sc=le;
		return;
	}
	build(2*node,le,(le+ri)/2);
	build(2*node+1,(le+ri)/2+1,ri);
	if(tree[2*node].f>tree[2*node+1].f) tree[node]=tree[2*node];
	else tree[node]=tree[2*node+1];
}
void update(ll node,ll le,ll ri,ll start,ll end,ll val) {
	if(lz[node]) {
		tree[node].f+=lz[node];
		if(le!=ri) {
			lz[2*node]+=lz[node];
			lz[2*node+1]+=lz[node];
		}
		lz[node]=0;
	}
	if(ri<start || le>end) return;
	if(start<=le && ri<=end) {
		tree[node].f+=val;
		if(le!=ri) {
			lz[2*node]+=val;
			lz[2*node+1]+=val;
		}	
		return;
	}
	update(2*node,le,(le+ri)/2,start,end,val);
	update(2*node+1,(le+ri)/2+1,ri,start,end,val);
	if(tree[2*node].f>tree[2*node+1].f) tree[node]=tree[2*node];
	else tree[node]=tree[2*node+1];
}
pair <ll,ll> getmax(ll node,ll le,ll ri,ll start,ll end) {
	if(lz[node]) {
		tree[node].f+=lz[node];
		if(le!=ri) {
			lz[2*node]+=lz[node];
			lz[2*node+1]+=lz[node];
		}
		lz[node]=0;
	}
	if(ri<start || le>end) return {-1,-1};
	if(start<=le && ri<=end) { return tree[node]; }
	pair <ll,ll> pr1=getmax(2*node,le,(le+ri)/2,start,end);
	pair <ll,ll> pr2=getmax(2*node+1,(le+ri)/2+1,ri,start,end);
	if(pr1.f>pr2.f) return pr1;
	else return pr2;
}
void dfs(ll x,ll y,ll dist) {
	//cout<<x<<" "<<y<<" "<<dist<<endl;
	t++;
	in[x]=t;
	D[x]=dist;
	P[x]=y;
	inv[t]=x;
	down[x]=D[x]-D[y];
	if(x!=maxroot && v[x].size()==1 && maxroot!=0) fotlebi++;
	update(1,1,n,in[x],in[x],D[x]);
	//cout<<x<<" "<<in[x]<<" "<<D[x]<<endl;
	for(ll i=0;i<v[x].size();i++) {
		if(v[x][i].f==y) continue;
		dfs(v[x][i].f,x,dist+v[x][i].sc.f);
		wvrt+=v[x][i].sc.sc;
	}
	out[x]=t;
}
void dfs1(ll x,ll y) {
	ans[1]=max(ans[1],wvrt);
	pr=getmax(1,1,n,1,n);
	//cout<<x<<"_"<<wvrt<<"_"<<pr.f<<endl;
	if(ans[2]<wvrt+pr.f) { ans[2]=wvrt+pr.f; maxroot=x; }
	for(ll i=0;i<v[x].size();i++) {
		if(v[x][i].f==y) continue;
		ll yx=v[x][i].sc.f; ll xy=v[x][i].sc.sc;
		wvrt=wvrt+yx-xy;
		update(1,1,n,in[v[x][i].f],out[v[x][i].f],-yx);
		update(1,1,n,1,in[v[x][i].f]-1,xy);
		update(1,1,n,out[v[x][i].f]+1,n,xy);		
		dfs1(v[x][i].f,x);
		wvrt=wvrt-yx+xy;
		update(1,1,n,in[v[x][i].f],out[v[x][i].f],+yx);
		update(1,1,n,1,in[v[x][i].f]-1,-xy);
		update(1,1,n,out[v[x][i].f]+1,n,-xy);
	}
}
int main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(ll i=1;i<n;i++) {
		cin>>A[i].f.f>>A[i].f.sc>>A[i].sc.f>>A[i].sc.sc;
		v[A[i].f.f].pb({A[i].f.sc,{A[i].sc.f,A[i].sc.sc}});
		v[A[i].f.sc].pb({A[i].f.f,{A[i].sc.sc,A[i].sc.f}});
		sum+=A[i].sc.f+A[i].sc.sc;
	}
	build(1,1,n);
	
	dfs(1,0,0);
	//cout<<"*"; return 0;
	dfs1(1,0);
	build(1,1,n);
	t=0;
	//cout<<maxroot<<endl;
	dfs(maxroot,0,0);
	for(ll i=2;i<=fotlebi+1;i++) {
		pr=getmax(1,1,n,1,n);
		if(i!=2) ans[i]=ans[i-1]+pr.f;
		//cout<<ans[i]<<" ";
		idx=inv[pr.sc];
		//cout<<pr.f<<" "<<pr.sc<<" "<<idx<<endl;
		while(idx!=maxroot && fix[idx]==0) {
			fix[idx]=1;
			update(1,1,n,in[idx],out[idx],-down[idx]);
			idx=P[idx];
		}
	}
	cin>>t;
	while(t--) {
		cin>>f;
		if(f>fotlebi) cout<<0<<endl;
		else cout<<sum-ans[f]<<endl;
	}
}
/*
4
1 2 1 2
1 3 3 4
1 4 5 6
2
1
2
*/

Compilation message (stderr)

designated_cities.cpp: In function 'void dfs(long long int, long long int, long long int)':
designated_cities.cpp:77:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(ll i=0;i<v[x].size();i++) {
      |             ~^~~~~~~~~~~~
designated_cities.cpp: In function 'void dfs1(long long int, long long int)':
designated_cities.cpp:89:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for(ll i=0;i<v[x].size();i++) {
      |             ~^~~~~~~~~~~~

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