Submission #388702

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
388702	2021-04-12T16:14:13 Z	1bin	Designated Cities (JOI19_designated_cities)	C++17	9 / 100	1092 ms	45952 KB

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 = 0, 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 < tmp) swap(mx, tmp);
		if (tmp) v.emplace_back(tmp, r);
	}
	return mx;
}

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;
		ll k = go(nxt, ct, nxt);
		v.emplace_back(k + e.second, nxt);
	}

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

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


	x = dp[ct];
	int h = v.size();
	for (int i = 0; i < v.size(); i++) {
		if (v[i].second != v[0].second) {
			h = i;
			break;
		}
	}
	if (h == v.size()) return;
	x -= v[h].first;
	for (int i = 1; i <= h; i++) {
		if (i > 1) ans[i] = min(ans[i], x);
		x -= v[i - 1].first;
	}
	for (int i = h + 1; i <= v.size(); i++) {
		ans[i] = min(ans[i], x);
		if (i < v.size()) x += v[i].first;
	}

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

designated_cities.cpp: In function 'void sol(int)':
designated_cities.cpp:89: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]
   89 |  for (int i = 0; i <= v.size(); i++) {
      |                  ~~^~~~~~~~~~~
designated_cities.cpp:91:9: 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 |   if (i < v.size()) x -= v[i].first;
      |       ~~^~~~~~~~~~
designated_cities.cpp:97: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]
   97 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
designated_cities.cpp:103:8: 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]
  103 |  if (h == v.size()) return;
      |      ~~^~~~~~~~~~~
designated_cities.cpp:109:24: 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 = h + 1; i <= v.size(); i++) {
      |                      ~~^~~~~~~~~~~
designated_cities.cpp:111:9: 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]
  111 |   if (i < v.size()) x += v[i].first;
      |       ~~^~~~~~~~~~

Subtask #1
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	6556 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	4 ms	6604 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	6560 KB	Output is correct
2	Correct	755 ms	32288 KB	Output is correct
3	Correct	1092 ms	45952 KB	Output is correct
4	Correct	772 ms	30980 KB	Output is correct
5	Correct	395 ms	32540 KB	Output is correct
6	Correct	905 ms	34592 KB	Output is correct
7	Correct	285 ms	34648 KB	Output is correct
8	Correct	1056 ms	40500 KB	Output is correct
9	Correct	220 ms	32864 KB	Output is correct