oj.uz

Submission #388709

# Submission time Handle Problem Language Result Execution time Memory
388709 2021-04-12T16:23:34 Z 1bin Designated Cities (JOI19_designated_cities) C++14
16 / 100
 1121 ms 39656 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(v.rbegin(), v.rend());

	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:87: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]
   87 |  for (int i = 1; i <= v.size(); i++) {
      |                  ~~^~~~~~~~~~~
designated_cities.cpp:95: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]
   95 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
designated_cities.cpp:108: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]
  108 |   for (int i = 0; i < v.size(); i++) {
      |                   ~~^~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6604 KB Output is correct
2 Incorrect 4 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 6604 KB Output is correct
2 Correct 762 ms 25980 KB Output is correct
3 Correct 1121 ms 37536 KB Output is correct
4 Correct 721 ms 25912 KB Output is correct
5 Correct 431 ms 26044 KB Output is correct
6 Correct 977 ms 28108 KB Output is correct
7 Correct 335 ms 26048 KB Output is correct
8 Correct 1090 ms 38308 KB Output is correct
9 Correct 234 ms 26864 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 825 ms 25908 KB Output is correct
3 Correct 1073 ms 39656 KB Output is correct
4 Correct 747 ms 26084 KB Output is correct
5 Correct 378 ms 26164 KB Output is correct
6 Correct 917 ms 28224 KB Output is correct
7 Correct 245 ms 28328 KB Output is correct
8 Correct 1050 ms 34100 KB Output is correct
9 Correct 237 ms 26792 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6604 KB Output is correct
2 Incorrect 4 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 6604 KB Output is correct
2 Correct 762 ms 25980 KB Output is correct
3 Correct 1121 ms 37536 KB Output is correct
4 Correct 721 ms 25912 KB Output is correct
5 Correct 431 ms 26044 KB Output is correct
6 Correct 977 ms 28108 KB Output is correct
7 Correct 335 ms 26048 KB Output is correct
8 Correct 1090 ms 38308 KB Output is correct
9 Correct 234 ms 26864 KB Output is correct
10 Correct 4 ms 6604 KB Output is correct
11 Correct 825 ms 25908 KB Output is correct
12 Correct 1073 ms 39656 KB Output is correct
13 Correct 747 ms 26084 KB Output is correct
14 Correct 378 ms 26164 KB Output is correct
15 Correct 917 ms 28224 KB Output is correct
16 Correct 245 ms 28328 KB Output is correct
17 Correct 1050 ms 34100 KB Output is correct
18 Correct 237 ms 26792 KB Output is correct
19 Correct 4 ms 6604 KB Output is correct
20 Incorrect 785 ms 26000 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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