Submission #615557

#	Time	Username	Problem	Language	Result	Execution time	Memory
615557		valerikk	Designated Cities (JOI19_designated_cities)	C++17	23 / 100	2070 ms	28872 KiB

designated_cities

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 7;

struct Edge {
	int v, a, b;

	Edge() {}

	Edge(int v_, int a_, int b_) : v(v_), a(a_), b(b_) {}
};

int n;
vector<Edge> e[N];
bool used[N];
int sz[N];
long long ans[N];

void dfs(int u, int p = -1) {
	sz[u] = 1;
	for (auto [v, a, b] : e[u]) {
		if (!used[v] && v != p) {
			dfs(v, u);
			sz[u] += sz[v];
		}
	}
}

int centroid(int u, int all, int p = -1) {
	for (auto [v, a, b] : e[u]) {
		if (!used[v] && v != p && 2 * sz[v] > all) {
			return centroid(v, all, u);
		}
	}
	return u;
}

long long zhfs(int u, int p = -1) {
	long long res = 0;
	for (auto [v, a, b] : e[u]) {
		if (!used[v] && v != p) {
			res += zhfs(v, u);
			res += b;
		}
	}
	return res;
}

long long go(int u, vector<long long> &d, int p = -1) {
	vector<long long> cur;
	for (auto [v, a, b] : e[u]) {
		if (!used[v] && v != p) {
			cur.push_back(go(v, d, u) + a);
		}
	}
	if (cur.empty()) return 0;
	swap(cur[0], cur[max_element(begin(cur), end(cur)) - begin(cur)]);
	for (int i = 1; i < (int)cur.size(); ++i) {
		d.push_back(cur[i]);
	}
	return cur[0];
}

void solve(int u, long long bonus) {
	dfs(u);
	vector<pair<long long, int>> ch;
	ch.reserve(e[u].size());
	for (auto [v, a, b] : e[u]) {
		if (!used[v]) {
			long long z = zhfs(v, u);
			bonus += b;
			bonus += z;
			ch.emplace_back(a - z - b, v);
		}
	}
	{
		vector<long long> d;
		d.reserve(sz[u]);
		long long dd = go(u, d);
		d.push_back(dd);
		sort(rbegin(d), rend(d));
		long long cur = 0;
		ans[1] = max(ans[1], bonus);
		for (int i = 0; i < (int)d.size(); ++i) {
			cur += d[i];
			ans[i + 2] = max(ans[i + 2], bonus + cur);
		}
	}
	used[u] = true; 
	{
		vector<pair<long long, int>> d;
		d.reserve(sz[u]);
		for (auto [v, a, b] : e[u]) {
			vector<long long> cur_d;
			cur_d.reserve(sz[v]);
			d.emplace_back(go(v, cur_d) + a, v);
			for (auto dd : cur_d) {
				d.emplace_back(dd, v);
			}
		}	
		sort(rbegin(d), rend(d));
		int f = -1;
		for (int i = 1; i < (int)d.size(); ++i) {
			if (d[i].second != d[0].second) {
				f = i;
				break;
			}
		}
		if (f != -1) {
			long long cur = 0;
			for (int i = 0; i < (int)d.size(); ++i) {
				cur += d[i].first;
				ans[i + 1 + (i < f)] = max(ans[i + 1 + (i < f)], cur + (i < f ? d[f].first : 0) + bonus);
			}
		}
	}
	for (auto [delta, v] : ch) {
		bonus += delta;
		solve(centroid(v, sz[v]), bonus);
		bonus -= delta;
	}
}

int main() {
	scanf("%d", &n);
	long long sum = 0;
	for (int i = 0; i < n - 1; ++i) {
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		--a, --b;
		e[a].emplace_back(b, c, d);
		e[b].emplace_back(a, d, c);
		sum += c;
		sum += d;
	}
	dfs(0);
	solve(centroid(0, n), 0);
	for (int i = 1; i <= n; ++i) {
		ans[i] = sum - ans[i];
	}
	for (int i = 2; i <= n; ++i) {
		ans[i] = min(ans[i], ans[i - 1]);
	}
	int q;
	scanf("%d", &q);
	while (q--) {
		int x;
		scanf("%d", &x);
		cout << ans[x] << "\n";
	}
	return 0;
}

Compilation message (stderr)

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
designated_cities.cpp:131:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |   scanf("%d%d%d%d", &a, &b, &c, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:147:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
designated_cities.cpp:150:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |   scanf("%d", &x);
      |   ~~~~~^~~~~~~~~~

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