Submission #388726

#	Time	Username	Problem	Language	Result	Execution time	Memory
388726		1bin	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	1131 ms	39888 KiB

designated_cities

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll NMAX = 2e5 + 5;
#define all(v) v.begin(), v.end()
ll N, Q, a, b, c, d, W[NMAX], vis[NMAX], dp[NMAX], U[NMAX], D[NMAX], ans[NMAX];
vector<pair<ll, ll>> to[NMAX], v;

void dfs2(int now, int bef) {
	for (auto& e : to[now]) {
		int nxt = e.first;
		if (nxt == bef) {
			U[now] += e.second;
			continue;
		}
		dfs2(nxt, now);
		D[now] += D[nxt] + e.second;
	}
	return;
}

void dfs3(int now, int bef) {
	for (auto& e : to[now]) {
		int nxt = e.first;
		if (nxt == bef) continue;
		U[nxt] += U[now] + D[now] - D[nxt] - e.second;
		dfs3(nxt, now);
	}
	return;
}

void init() {
	dfs2(1, -1); dfs3(1, -1);
	for (int i = 1; i <= N; i++) dp[i] = U[i] + D[i];
	return;
}

int dfs(int now, int bef) {
	W[now] = 1;
	for (auto& e : to[now]) {
		int nxt = e.first;
		if (nxt == bef || vis[nxt]) continue;
		W[now] += dfs(nxt, now);
	}
	return W[now];
}

int centroid(int now, int bef, int lim) {
	for (auto& e : to[now]) {
		int nxt = e.first;
		if (nxt == bef || vis[nxt]) continue;
		if (W[nxt] > lim) return centroid(nxt, now, lim);
	}
	return now;
}

ll go(int now, int bef, int r) {
	ll mx = -1, tmp;
	for (auto& e : to[now]) {
		int nxt = e.first;
		if (nxt == bef || vis[nxt]) continue;
		tmp = go(nxt, now, r) + e.second;
		if (mx == -1) mx = tmp;
		else {
			if (mx < tmp) swap(mx, tmp);
			if (tmp) v.emplace_back(tmp, r);
		}
	}
	return max(mx, 0LL);
}

void sol(int r) {
	int lim = dfs(r, -1) / 2;
	int ct = centroid(r, -1, lim);
	vis[ct] = 1;

	v.clear();
	for (auto& e : to[ct]) {
		int nxt = e.first;
		if (vis[nxt]) continue;
		v.emplace_back(go(nxt, ct, nxt) + e.second, nxt);
	}

	sort(all(v));
	reverse(all(v));

	ll x = dp[ct];
	ans[1] = min(ans[1], x);
	for (int i = 1; i <= v.size(); i++) {
		x -= v[i - 1].first;
		ans[i + 1] = min(ans[i + 1], x);
	}


	x = dp[ct];
	ll a = b = 0, cnt;
	for (int i = 1; i < v.size(); i++) {
		if (v[a].second != v[i].second) {
			b = i; break;
		}
	}

	if (b) {
		x -= v[a].first + v[b].first;
		ans[2] = min(ans[2], x);
		cnt = 2;
		for (int i = 0; i < v.size(); i++) {
			if (i == a || i == b) continue;
			cnt++; x -= v[i].first;
			ans[cnt] = min(ans[cnt], x);
		}
	}

	for (auto& e : to[ct]) {
		int nxt = e.first;
		if (vis[nxt]) continue;
		sol(nxt);
	}
	return;
}

int main(void) {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		cin >> a >> b >> c >> d;
		to[a].emplace_back(b, c);
		to[b].emplace_back(a, d);
	}

	init();
	/*for (int i = 1; i <= N; i++) cout << dp[i] << ' ';
	return 0;*/

	fill(ans, ans + NMAX, 1e18);
	sol(1);
	for (int i = 2; i <= N; i++) ans[i] = min(ans[i], ans[i - 1]);
	cin >> Q;
	int k;
	while (Q--) {
		cin >> k;
		cout << ans[k] << '\n';
	}
	return 0;
}

Compilation message (stderr)

designated_cities.cpp: In function 'void sol(int)':
designated_cities.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for (int i = 1; i <= v.size(); i++) {
      |                  ~~^~~~~~~~~~~
designated_cities.cpp:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |  for (int i = 1; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
designated_cities.cpp:109:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   for (int i = 0; i < v.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