Submission #383767

#	Time	Username	Problem	Language	Result	Execution time	Memory
383767		rqi	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	1947 ms	46352 KiB

designated_cities

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
typedef vector<int> vi;
typedef vector<ll> vl;
 
#define f first
#define s second
#define mp make_pair
#define pb push_back
 
#define sz(x) (int)(x).size()
 
void ckmax(ll&a, ll b){
	a = max(a, b);
}
 
const int mx = 200005;
int N;
int A[mx];
int B[mx];
ll C[mx];
ll D[mx];
int E[mx];
 
vector<pair<int, ll>> adj[mx];
ll tot_cost;
ll ans[mx];
 
int sub[mx];
vi cen_nodes;
 
void genSub(int node, int p = -1){
	cen_nodes.pb(node);
	sub[node] = 1;
	for(auto u: adj[node]){
		if(u.f == p) continue;
		genSub(u.f, node);
		sub[node]+=sub[u.f];
	}
}
 
int getCen(int node, int tot_sz, int p = -1){
	for(auto u: adj[node]){
		if(u.f == p) continue;
		if(sub[u.f] > tot_sz/2) return getCen(u.f, tot_sz, node);
	}
	return node;
}
 
 
 
int genCen(int node){
	cen_nodes.clear();
	genSub(node);
	return getCen(node, sub[node]);
}
 
pair<int, ll> par[mx];
ll sum_up[mx];
pair<ll, int> best_down[mx];
 
void genUpDown(int node, int p = -1){
	sum_up[node] = 0;
	best_down[node] = mp(0, node);
 
	for(auto u: adj[node]){
		if(u.f == p) continue;
		ll bedge = 0;
		for(auto x: adj[u.f]){
			if(x.f == node){
				bedge = x.s;
				break;
			}
		}
		par[u.f] = mp(node, u.s);
		sum_up[node]+=bedge;
		genUpDown(u.f, node);
		sum_up[node]+=sum_up[u.f];
		best_down[node] = max(best_down[node], mp(best_down[u.f].f+u.s, best_down[u.f].s));
	}
}
 
bool taken[mx];
vl sums;
 
void genAns(int cen, ll offset){
	cen = genCen(cen);
 
	//process cen
 
	genUpDown(cen);
 
	//update ans - remember done/offset
 
	//cout << "cen, offset, sumup[cen]: " << cen << " " << offset << " " << sum_up[cen] << "\n";
 
	ckmax(ans[1], sum_up[cen]+offset);

 
	queue<int> q;
	ll val1 = 0;
	ll val2 = 0;
	for(auto &u: adj[cen]){
		q.push(best_down[u.f].s);
		ckmax(val2, best_down[u.f].f+par[u.f].s);
		if(val1 < val2){
			swap(val1, val2);
		}
	}
 
	for(auto &u: cen_nodes){
		taken[u] = 0;
	}
	taken[cen] = 1;
 
	while(sz(sums)) sums.pop_back();

	while(sz(q)){
		int take_node = q.front();
		q.pop();
 
		//cout << "take_node: " << i << " " << take_node << "\n";
		ll sum = 0;
		while(true){
			sum+=par[take_node].s;
			taken[take_node] = 1;
			//cout << "add: " << take_node << " " << par[take_node].s << "\n";
			for(auto u: adj[take_node]){
				if(taken[u.f] || u.f == par[take_node].f) continue;
				q.push(best_down[u.f].s);
				//cout << "push: " << best_down[u.f].s << "\n";
			}
			if(taken[par[take_node].f]) break;
			take_node = par[take_node].f;
		}
		sums.pb(sum);
	}


	sort(sums.rbegin(), sums.rend());
	// cout << "sums: ";
	// for(auto u: sums){
	// 	cout << u << " ";
	// }
	// cout << "\n";

	//cout << "vals: " << val1 << " " << val2 << "\n";

	ll cur_sum = 0;
	for(int i = 1; i <= sz(cen_nodes); i++){
		if(i-1 >= sz(sums)){
			ckmax(ans[i], cur_sum+offset+sum_up[cen]);
			continue;
		}
		cur_sum+=sums[i-1];

		if(i == 1) continue;

		if(sums[i-1] > val2){
			//cout << i+1 << " " << cur_sum+val2+offset+sum_up[cen] << "\n";
			ckmax(ans[i+1], cur_sum+val2+offset+sum_up[cen]);
		}
		else{
			ckmax(ans[i], cur_sum+offset+sum_up[cen]);
		}
	}

 
	//recurse
	for(auto u: adj[cen]){
		ll new_offset = offset+sum_up[cen]-sum_up[u.f]+u.s;
		vector<pair<int, ll>> v;
		for(auto x: adj[u.f]){
			if(x.f == cen){
				new_offset-=x.s;
				continue;
			}
			v.pb(x);
		}
		adj[u.f] = v;
		genAns(u.f, new_offset);
	}
}
 
int main(){
	cin >> N;
	for(int i = 1; i <= N-1; i++){
		cin >> A[i] >> B[i] >> C[i] >> D[i];
		adj[A[i]].pb(mp(B[i], C[i]));
		adj[B[i]].pb(mp(A[i], D[i]));
		tot_cost+=C[i]+D[i];
	}
 
	genAns(1, 0);
 
	// cout << "tot: " << tot_cost << "\n";
	// for(int i = 1; i <= N; i++){
	// 	cout << "i, ans[i]: " << i << " " << ans[i] << "\n";
	// }
 
	for(int i = 1; i <= N; i++){
		ans[i] = tot_cost-ans[i];
	}
 
	//cout << ans[N] << "\n";
 
	assert(ans[N] == 0);
 
	int Q;
	cin >> Q;
	for(int i = 1; i <= Q; i++){
		cin >> E[i];
		cout << ans[E[i]] << "\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