oj.uz

Submission #388725

# Submission time Handle Problem Language Result Execution time Memory
388725 2021-04-12T16:59:29 Z 1bin Designated Cities (JOI19_designated_cities) C++14
100 / 100
 1222 ms 40064 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], 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];
	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()) {
		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;
		}
	}
	
	/*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);

	//freopen("input.txt", "r", stdin);
	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:105: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]
  105 |  if (h != v.size()) {
      |      ~~^~~~~~~~~~~
designated_cities.cpp:111:25: 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 |   for (int i = h + 1; i <= v.size(); i++) {
      |                       ~~^~~~~~~~~~~
designated_cities.cpp:113:10: 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]
  113 |    if (i < v.size()) x -= v[i].first;
      |        ~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6604 KB Output is correct
2 Correct 4 ms 6604 KB Output is correct
3 Correct 5 ms 6604 KB Output is correct
4 Correct 5 ms 6568 KB Output is correct
5 Correct 4 ms 6608 KB Output is correct
6 Correct 5 ms 6560 KB Output is correct
7 Correct 4 ms 6604 KB Output is correct
8 Correct 4 ms 6604 KB Output is correct
9 Correct 4 ms 6604 KB Output is correct
10 Correct 4 ms 6604 KB Output is correct
11 Correct 4 ms 6568 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Correct 762 ms 25988 KB Output is correct
3 Correct 1055 ms 37572 KB Output is correct
4 Correct 730 ms 25904 KB Output is correct
5 Correct 390 ms 26096 KB Output is correct
6 Correct 923 ms 27904 KB Output is correct
7 Correct 364 ms 26144 KB Output is correct
8 Correct 1079 ms 38312 KB Output is correct
9 Correct 241 ms 26792 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6532 KB Output is correct
2 Correct 807 ms 25932 KB Output is correct
3 Correct 1148 ms 39664 KB Output is correct
4 Correct 853 ms 26076 KB Output is correct
5 Correct 392 ms 26068 KB Output is correct
6 Correct 990 ms 28264 KB Output is correct
7 Correct 250 ms 28380 KB Output is correct
8 Correct 1159 ms 34108 KB Output is correct
9 Correct 225 ms 26764 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6604 KB Output is correct
2 Correct 4 ms 6604 KB Output is correct
3 Correct 5 ms 6604 KB Output is correct
4 Correct 5 ms 6568 KB Output is correct
5 Correct 4 ms 6608 KB Output is correct
6 Correct 5 ms 6560 KB Output is correct
7 Correct 4 ms 6604 KB Output is correct
8 Correct 4 ms 6604 KB Output is correct
9 Correct 4 ms 6604 KB Output is correct
10 Correct 4 ms 6604 KB Output is correct
11 Correct 4 ms 6568 KB Output is correct
12 Correct 4 ms 6604 KB Output is correct
13 Correct 7 ms 6908 KB Output is correct
14 Correct 8 ms 6976 KB Output is correct
15 Correct 7 ms 6880 KB Output is correct
16 Correct 7 ms 6816 KB Output is correct
17 Correct 7 ms 6860 KB Output is correct
18 Correct 7 ms 6860 KB Output is correct
19 Correct 8 ms 6860 KB Output is correct
20 Correct 7 ms 6860 KB Output is correct
21 Correct 7 ms 6860 KB Output is correct
22 Correct 7 ms 6860 KB Output is correct
23 Correct 7 ms 6860 KB Output is correct
24 Correct 8 ms 6840 KB Output is correct
25 Correct 7 ms 6996 KB Output is correct
26 Correct 7 ms 6860 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6476 KB Output is correct
2 Correct 762 ms 25988 KB Output is correct
3 Correct 1055 ms 37572 KB Output is correct
4 Correct 730 ms 25904 KB Output is correct
5 Correct 390 ms 26096 KB Output is correct
6 Correct 923 ms 27904 KB Output is correct
7 Correct 364 ms 26144 KB Output is correct
8 Correct 1079 ms 38312 KB Output is correct
9 Correct 241 ms 26792 KB Output is correct
10 Correct 4 ms 6532 KB Output is correct
11 Correct 807 ms 25932 KB Output is correct
12 Correct 1148 ms 39664 KB Output is correct
13 Correct 853 ms 26076 KB Output is correct
14 Correct 392 ms 26068 KB Output is correct
15 Correct 990 ms 28264 KB Output is correct
16 Correct 250 ms 28380 KB Output is correct
17 Correct 1159 ms 34108 KB Output is correct
18 Correct 225 ms 26764 KB Output is correct
19 Correct 4 ms 6604 KB Output is correct
20 Correct 777 ms 25976 KB Output is correct
21 Correct 1222 ms 40064 KB Output is correct
22 Correct 801 ms 26100 KB Output is correct
23 Correct 793 ms 26440 KB Output is correct
24 Correct 803 ms 26432 KB Output is correct
25 Correct 831 ms 26556 KB Output is correct
26 Correct 794 ms 26416 KB Output is correct
27 Correct 397 ms 26256 KB Output is correct
28 Correct 985 ms 27992 KB Output is correct
29 Correct 739 ms 26520 KB Output is correct
30 Correct 657 ms 26312 KB Output is correct
31 Correct 324 ms 26776 KB Output is correct
32 Correct 1198 ms 34804 KB Output is correct
33 Correct 223 ms 26880 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6604 KB Output is correct
2 Correct 4 ms 6604 KB Output is correct
3 Correct 5 ms 6604 KB Output is correct
4 Correct 5 ms 6568 KB Output is correct
5 Correct 4 ms 6608 KB Output is correct
6 Correct 5 ms 6560 KB Output is correct
7 Correct 4 ms 6604 KB Output is correct
8 Correct 4 ms 6604 KB Output is correct
9 Correct 4 ms 6604 KB Output is correct
10 Correct 4 ms 6604 KB Output is correct
11 Correct 4 ms 6568 KB Output is correct
12 Correct 4 ms 6476 KB Output is correct
13 Correct 762 ms 25988 KB Output is correct
14 Correct 1055 ms 37572 KB Output is correct
15 Correct 730 ms 25904 KB Output is correct
16 Correct 390 ms 26096 KB Output is correct
17 Correct 923 ms 27904 KB Output is correct
18 Correct 364 ms 26144 KB Output is correct
19 Correct 1079 ms 38312 KB Output is correct
20 Correct 241 ms 26792 KB Output is correct
21 Correct 4 ms 6532 KB Output is correct
22 Correct 807 ms 25932 KB Output is correct
23 Correct 1148 ms 39664 KB Output is correct
24 Correct 853 ms 26076 KB Output is correct
25 Correct 392 ms 26068 KB Output is correct
26 Correct 990 ms 28264 KB Output is correct
27 Correct 250 ms 28380 KB Output is correct
28 Correct 1159 ms 34108 KB Output is correct
29 Correct 225 ms 26764 KB Output is correct
30 Correct 4 ms 6604 KB Output is correct
31 Correct 7 ms 6908 KB Output is correct
32 Correct 8 ms 6976 KB Output is correct
33 Correct 7 ms 6880 KB Output is correct
34 Correct 7 ms 6816 KB Output is correct
35 Correct 7 ms 6860 KB Output is correct
36 Correct 7 ms 6860 KB Output is correct
37 Correct 8 ms 6860 KB Output is correct
38 Correct 7 ms 6860 KB Output is correct
39 Correct 7 ms 6860 KB Output is correct
40 Correct 7 ms 6860 KB Output is correct
41 Correct 7 ms 6860 KB Output is correct
42 Correct 8 ms 6840 KB Output is correct
43 Correct 7 ms 6996 KB Output is correct
44 Correct 7 ms 6860 KB Output is correct
45 Correct 4 ms 6604 KB Output is correct
46 Correct 777 ms 25976 KB Output is correct
47 Correct 1222 ms 40064 KB Output is correct
48 Correct 801 ms 26100 KB Output is correct
49 Correct 793 ms 26440 KB Output is correct
50 Correct 803 ms 26432 KB Output is correct
51 Correct 831 ms 26556 KB Output is correct
52 Correct 794 ms 26416 KB Output is correct
53 Correct 397 ms 26256 KB Output is correct
54 Correct 985 ms 27992 KB Output is correct
55 Correct 739 ms 26520 KB Output is correct
56 Correct 657 ms 26312 KB Output is correct
57 Correct 324 ms 26776 KB Output is correct
58 Correct 1198 ms 34804 KB Output is correct
59 Correct 223 ms 26880 KB Output is correct
60 Correct 4 ms 6608 KB Output is correct
61 Correct 796 ms 27540 KB Output is correct
62 Correct 1186 ms 38112 KB Output is correct
63 Correct 792 ms 27528 KB Output is correct
64 Correct 747 ms 27736 KB Output is correct
65 Correct 753 ms 27508 KB Output is correct
66 Correct 833 ms 27752 KB Output is correct
67 Correct 798 ms 27684 KB Output is correct
68 Correct 454 ms 27780 KB Output is correct
69 Correct 967 ms 29364 KB Output is correct
70 Correct 934 ms 27800 KB Output is correct
71 Correct 700 ms 27744 KB Output is correct
72 Correct 373 ms 28324 KB Output is correct
73 Correct 1148 ms 34464 KB Output is correct
74 Correct 311 ms 28320 KB Output is correct