Submission #525442

#	Time	Username	Problem	Language	Result	Execution time	Memory
525442		mosiashvililuka	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	466 ms	49852 KiB

designated_cities

#include<bits/stdc++.h>
#define vla vector <pair <long long, pair <long long, long long> > >
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,C,D,dp[200009],dp2[200009],ans[200009],JM,DP2[200009],rt,dp3[200009],dp4[200009],p[200009],dep[200009],MSH[200009];
pair <long long, long long> DP[200009];
vla v[200009];
void dfs(int q, int w){
	for(vla::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it).first==w) continue;
		dfs((*it).first,q);
		dp[q]+=dp[(*it).first]+(*it).second.second;
	}
}
void dfs2(int q, int w){
	if(w!=0) dp2[q]=dp2[w]+dp[w]-dp[q]-C+D;
	for(vla::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it).first==w) continue;
		C=(*it).second.second;D=(*it).second.first;
		dfs2((*it).first,q);
	}
}
void upd(long long q, long long w){
	if(DP[q].first<=w){
		DP[q].second=DP[q].first;DP[q].first=w;
	}else{
		if(DP[q].second<w) DP[q].second=w;
	}
}
void dfs3(int q, int w){
	for(vla::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it).first==w) continue;
		dfs3((*it).first,q);
		upd(q,DP[(*it).first].first+(*it).second.first);
	}
}
void dfs4(int q, int w){
	if(w!=0){
	DP2[q]=DP2[w]+C;
	zx=0;
	if(DP[w].first!=DP[q].first+D){
		zx=DP[w].first+C;
	}else{
		zx=DP[w].second+C;
	}
	DP2[q]=max(DP2[q],zx);
	}
	for(vla::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it).first==w) continue;
		C=(*it).second.second;D=(*it).second.first;
		dfs4((*it).first,q);
	}
}
void dfs5(int q, int w){
	dp4[q]=q;
	for(vla::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it).first==w) continue;
		dep[(*it).first]=dep[q]+(*it).second.first;MSH[(*it).first]=(*it).second.first;
		dfs5((*it).first,q);
		if(dep[dp4[q]]<dep[dp4[(*it).first]]){
			dp4[q]=dp4[(*it).first];
		}
	}
	p[dp4[q]]+=MSH[q];
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;
	for(i=1; i<a; i++){
		cin>>c>>d>>C>>D;JM+=C+D;
		v[c].push_back({d,{C,D}});
		v[d].push_back({c,{D,C}});
	}
	dfs(1,0);
	C=0;D=0;
	dfs2(1,0);
	for(i=1; i<=a; i++){
		ans[1]=max(ans[1],dp[i]+dp2[i]);
	}
	dfs3(1,0);
	C=0;D=0;
	dfs4(1,0);
	for(i=1; i<=a; i++){
		zx=dp[i]+dp2[i];zx+=max(DP[i].first,DP2[i]);
		if(ans[2]<zx){
			ans[2]=zx;rt=i;
		}
	}
	//
	/*cout<<JM-ans[1]<<" "<<JM-ans[2]<<"\n";
	cout<<rt<<"\n";*/
	//
	dfs5(rt,0);
	sort(p+1,p+a+1);
	for(i=1; i<=a/2; i++) swap(p[i],p[a-i+1]);
	zx=dp[rt]+dp2[rt];
	for(i=2; i<=a; i++){
		zx+=p[i-1];
		ans[i]=zx;
	}
	cin>>tes;
	for(t=1; t<=tes; t++){
		cin>>c;
		cout<<JM-ans[c]<<"\n";
	}
	return 0;
}

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