Submission #1218506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218506		kookeudas	Designated Cities (JOI19_designated_cities)	C++20	100 / 100	492 ms	28264 KiB

designated_cities

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ld = long double;
int n,Q;
struct st{
	int node,c,cr;
};
vector<st> v[200002];
ll ans[200002];
vector<pair<ll,ll>> av;
int sub[200002];
bool cut[200002];
ll d0[200002];
	ll s = 0;
ll dfs(int node, int b, int ii, int rt){
	ll mx = 0;
	vector<pair<ll,ll>> t;
	for(st nxt:v[node])if(nxt.node!=b && !cut[nxt.node]){
		t.push_back({ii,dfs(nxt.node,node,ii,rt)+nxt.c});
		mx = max(mx,t[t.size()-1].second);
		if(node==rt)ii++;
	}
	bool tf=true;
	for(pair<ll,ll> ele:t){
		if(mx==ele.second && tf){
			tf=false;
			if(node==rt)av.push_back({ele.second,ele.first});
		}
		else{
			av.push_back({ele.second,ele.first});
		}
	}
	return mx;
}
ll dfs0(int node, int b){
	ll ret = 0;
	for(st nxt:v[node])if(nxt.node!=b){
		ret+=dfs0(nxt.node,node);
		ret+=nxt.cr;
	}
	return ret;
}
void dfs1(int node, int b, ll cur){
	d0[node] = cur;
	for(st nxt:v[node])if(nxt.node!=b){
		dfs1(nxt.node,node,cur+nxt.c-nxt.cr);
	}
}
void cdfs(int node, int b){
	sub[node] = 1;
	for(st nxt:v[node])if(nxt.node!=b && !cut[nxt.node]){
		cdfs(nxt.node,node);
		sub[node]+=sub[nxt.node];
	}
}
int getCent(int node, int b, int siz){
	for(st nxt:v[node])if(nxt.node!=b && !cut[nxt.node] && sub[nxt.node]*2>siz)return getCent(nxt.node,node,siz);
	return node;
}
void dnc(int node){
	cdfs(node,0);
	int cent = getCent(node,0,sub[node]);
	av.clear();
	dfs(cent,0,0,cent);
	ll cur = d0[cent];
	ans[1] = max(ans[1],cur);
	sort(av.begin(),av.end());
	reverse(av.begin(),av.end());
	int ch = 0;
	for(st nxt:v[cent])if(!cut[nxt.node])ch++;
	if(ch==1){
		for(int j=0;j<av.size();j++){
			cur+=av[j].first;
			ans[j+2] = max(ans[j+2],cur);
		}
	}
	else if(av.size()>=2){
		int k = -1;
		for(int j=1;j<av.size();j++){
			if(av[j].second!=av[0].second){
				k = j;
				cur+=av[j].first;
				break;
			}
		}
		assert(k!=-1);
		int cc = 1;
		for(int j=0;j<av.size();j++){
			if(j==k)continue;
			cur+=av[j].first;
			cc++;
			ans[cc] = max(ans[cc],cur);
		}
	}
	cut[cent] = 1;
	for(st nxt:v[cent])if(!cut[nxt.node])dnc(nxt.node);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=0;i<n-1;i++){
		int a,b,c,cr;
		cin>>a>>b>>c>>cr;
		v[a].push_back({b,c,cr});
		v[b].push_back({a,cr,c});
		s+=c+cr;
	}
	dfs1(1,0,dfs0(1,0));
	dnc(1);
	for(int i=1;i<=n;i++)ans[i] = max(ans[i],ans[i-1]);
	cin>>Q;
	while(Q--){
		int q;
		cin>>q;
		cout<<s-ans[q]<<'\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