Submission #383725

#	Time	Username	Problem	Language	Result	Execution time	Memory
383725		rqi	Designated Cities (JOI19_designated_cities)	C++14	56 / 100	2076 ms	53724 KiB

designated_cities

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

#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];

bool done[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 || done[u.f]) 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 || done[u.f]) 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];
bool active[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 || done[u.f]) continue;
		ll bedge = 0;
		for(auto x: adj[u.f]){
			if(done[x.f]) continue;
			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];

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);

	for(auto u: cen_nodes){
		taken[u] = 0;
		active[u] = 0;
	}
	taken[cen] = 1;

	priority_queue<pair<ll, int>> pq;
	for(auto u: adj[cen]){
		if(done[u.f]) continue;
		active[u.f] = 1;
	}

	vector<pair<ll, pi>> paths;
	for(auto u: cen_nodes){
		if(u == cen) continue;
		paths.pb(mp(best_down[u].f+par[u].s, mp(best_down[u].s, u)));
	}
	sort(paths.rbegin(), paths.rend());

	// cout << "paths:" << "\n";
	// for(auto u: paths){
	// 	cout << u.f << " " << u.s.f << " " << u.s.s << "\n";
	// }

	ll cur_sum = 0;
	ll best_outside = 0;
	bool good = 0;
	int cur_path_ind = 0;
	for(int i = 1; i <= sz(cen_nodes); i++){
		int take_node = -1;
		while(cur_path_ind < sz(paths)){
			if(!active[paths[cur_path_ind].s.s]){
				cur_path_ind++;
				continue;
			}
			take_node = paths[cur_path_ind].s.f;
			cur_path_ind++;
			break;
		}
		//cout << "i, take_node: " << i << " " << take_node << "\n";

		if(take_node == -1){
			ckmax(ans[i], cur_sum+sum_up[cen]+offset);
			//cout << "ckmax(ans[]: " << i << " " << cur_sum+sum_up[cen]+offset << "\n";
			continue;
		}
		assert(take_node != -1);
		//cout << "take_node: " << i << " " << take_node << "\n";
		while(true){
			cur_sum+=par[take_node].s;
			taken[take_node] = 1;
			//cout << "add: " << take_node << " " << par[take_node].s << " " << cur_sum << "\n";
			for(auto u: adj[take_node]){
				if(u.f == par[take_node].f || done[u.f] || taken[u.f]) continue;
				active[u.f] = 1;
				//cout << "push: " << best_down[u.f].s << "\n";
			}
			if(taken[par[take_node].f]) break;
			take_node = par[take_node].f;
		}
		
		if(i == 1){
			for(auto u: adj[cen]){
				if(done[u.f]) continue;
				if(u.f != take_node){
					ckmax(best_outside, u.s+best_down[u.f].f);
				}
			}
		}

		if(i != 1 && par[take_node].f == cen){
			good = 1;
		}

		if(good){
			ckmax(ans[i], cur_sum+sum_up[cen]+offset);
			//cout << "ckmax(ans[]: " << i << " " << cur_sum+sum_up[cen]+offset << "\n";
		}
		else{
			ckmax(ans[i+1], cur_sum+best_outside+sum_up[cen]+offset);
			//cout << "ckmax(ans[]: " << i+1 << " " << cur_sum+best_outside+sum_up[cen]+offset << "\n";
		}
	}

	//recurse

	done[cen] = 1;

	vector<pair<int, ll>> recurse;
	for(auto u: adj[cen]){
		if(done[u.f]) continue;
		ll new_offset = offset+sum_up[cen]-sum_up[u.f]+u.s;
		for(auto x: adj[u.f]){
			if(x.f == cen){
				new_offset-=x.s;
				break;
			}
		}
		recurse.pb(mp(u.f, new_offset));
	}

	for(auto u: recurse){
		genAns(u.f, u.s);
	}
}

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: 0 / 44