oj.uz

Submission #388704

# Submission time Handle Problem Language Result Execution time Memory
388704 2021-04-12T16:17:04 Z 1bin Designated Cities (JOI19_designated_cities) C++14
16 / 100
 1152 ms 44712 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 = -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 (tmp > mx) swap(mx, 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, 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: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 = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
designated_cities.cpp:112: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]
  112 |   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 6680 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 6604 KB Output is correct
2 Correct 724 ms 32364 KB Output is correct
3 Correct 1152 ms 44124 KB Output is correct
4 Correct 791 ms 30904 KB Output is correct
5 Correct 446 ms 32556 KB Output is correct
6 Correct 986 ms 34560 KB Output is correct
7 Correct 340 ms 32560 KB Output is correct
8 Correct 1105 ms 44712 KB Output is correct
9 Correct 231 ms 33252 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 808 ms 25892 KB Output is correct
3 Correct 1111 ms 39788 KB Output is correct
4 Correct 752 ms 25924 KB Output is correct
5 Correct 407 ms 26164 KB Output is correct
6 Correct 976 ms 28280 KB Output is correct
7 Correct 243 ms 28316 KB Output is correct
8 Correct 1079 ms 34252 KB Output is correct
9 Correct 242 ms 26848 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 6680 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 6604 KB Output is correct
2 Correct 724 ms 32364 KB Output is correct
3 Correct 1152 ms 44124 KB Output is correct
4 Correct 791 ms 30904 KB Output is correct
5 Correct 446 ms 32556 KB Output is correct
6 Correct 986 ms 34560 KB Output is correct
7 Correct 340 ms 32560 KB Output is correct
8 Correct 1105 ms 44712 KB Output is correct
9 Correct 231 ms 33252 KB Output is correct
10 Correct 4 ms 6604 KB Output is correct
11 Correct 808 ms 25892 KB Output is correct
12 Correct 1111 ms 39788 KB Output is correct
13 Correct 752 ms 25924 KB Output is correct
14 Correct 407 ms 26164 KB Output is correct
15 Correct 976 ms 28280 KB Output is correct
16 Correct 243 ms 28316 KB Output is correct
17 Correct 1079 ms 34252 KB Output is correct
18 Correct 242 ms 26848 KB Output is correct
19 Correct 4 ms 6604 KB Output is correct
20 Incorrect 767 ms 32376 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 6680 KB Output isn't correct
3 Halted 0 ms 0 KB -