oj.uz

Submission #388705

# Submission time Handle Problem Language Result Execution time Memory
388705 2021-04-12T16:21:06 Z 1bin Designated Cities (JOI19_designated_cities) C++14
16 / 100
 1100 ms 39648 KB 
#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], p[NMAX], pp[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;
		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, idx, cnt;
	for (int i = 0; i < v.size(); i++) {
		idx = v[i].second;
		if (!a) {
			a = idx; x -= v[i].first;
		}
		else if (a != idx) {
			b = idx; x -= v[i].first; break;
		}
	}

	if (b) {
		ans[2] = min(ans[2], x);
		cnt = 2;
		for (int i = 0; i < v.size(); i++) {
			idx = v[i].second;
			if (idx == a || idx == 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

designated_cities.cpp: In function 'void sol(int)':
designated_cities.cpp:88: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]
   88 |  for (int i = 1; i <= v.size(); i++) {
      |                  ~~^~~~~~~~~~~
designated_cities.cpp:96: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]
   96 |  for (int i = 0; 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
0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6608 KB Output is correct
2 Correct 741 ms 26120 KB Output is correct
3 Correct 1090 ms 37536 KB Output is correct
4 Correct 731 ms 25908 KB Output is correct
5 Correct 404 ms 26100 KB Output is correct
6 Correct 917 ms 28068 KB Output is correct
7 Correct 359 ms 26084 KB Output is correct
8 Correct 1100 ms 38152 KB Output is correct
9 Correct 219 ms 26780 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6604 KB Output is correct
2 Correct 770 ms 26016 KB Output is correct
3 Correct 1095 ms 39648 KB Output is correct
4 Correct 825 ms 26004 KB Output is correct
5 Correct 409 ms 26196 KB Output is correct
6 Correct 984 ms 28188 KB Output is correct
7 Correct 254 ms 28376 KB Output is correct
8 Correct 1069 ms 34052 KB Output is correct
9 Correct 222 ms 26792 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6608 KB Output is correct
2 Correct 741 ms 26120 KB Output is correct
3 Correct 1090 ms 37536 KB Output is correct
4 Correct 731 ms 25908 KB Output is correct
5 Correct 404 ms 26100 KB Output is correct
6 Correct 917 ms 28068 KB Output is correct
7 Correct 359 ms 26084 KB Output is correct
8 Correct 1100 ms 38152 KB Output is correct
9 Correct 219 ms 26780 KB Output is correct
10 Correct 4 ms 6604 KB Output is correct
11 Correct 770 ms 26016 KB Output is correct
12 Correct 1095 ms 39648 KB Output is correct
13 Correct 825 ms 26004 KB Output is correct
14 Correct 409 ms 26196 KB Output is correct
15 Correct 984 ms 28188 KB Output is correct
16 Correct 254 ms 28376 KB Output is correct
17 Correct 1069 ms 34052 KB Output is correct
18 Correct 222 ms 26792 KB Output is correct
19 Correct 4 ms 6604 KB Output is correct
20 Incorrect 756 ms 25880 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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