oj.uz

Submission #615568

# Submission time Handle Problem Language Result Execution time Memory
615568 2022-07-31T10:42:31 Z valerikk Designated Cities (JOI19_designated_cities) C++17
7 / 100
 1067 ms 33928 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 7;

struct Edge {
	int v, a, b;

	Edge() {}

	Edge(int v_, int a_, int b_) : v(v_), a(a_), b(b_) {}
};

int n;
vector<Edge> e[N];
bool used[N];
int sz[N];
long long ans[N];

void dfs(int u, int p = -1) {
	sz[u] = 1;
	for (auto [v, a, b] : e[u]) {
		if (!used[v] && v != p) {
			dfs(v, u);
			sz[u] += sz[v];
		}
	}
}

int centroid(int u, int all, int p = -1) {
	for (auto [v, a, b] : e[u]) {
		if (!used[v] && v != p && 2 * sz[v] > all) {
			return centroid(v, all, u);
		}
	}
	return u;
}

long long zhfs(int u, int p = -1) {
	long long res = 0;
	for (auto [v, a, b] : e[u]) {
		if (!used[v] && v != p) {
			res += zhfs(v, u);
			res += b;
		}
	}
	return res;
}

long long go(int u, int t, vector<pair<long long, int>> &d, int p = -1) {
	vector<long long> cur;
	for (auto [v, a, b] : e[u]) {
		if (!used[v] && v != p) {
			cur.push_back(go(v, t, d, u) + a);
		}
	}
	if (cur.empty()) return 0;
	swap(cur[0], cur[max_element(begin(cur), end(cur)) - begin(cur)]);
	for (int i = 1; i < (int)cur.size(); ++i) {
		d.emplace_back(cur[i], t);
	}
	return cur[0];
}

void solve(int u, long long bonus) {
	dfs(u);
	vector<pair<long long, int>> ch;
	ch.reserve(e[u].size());
	for (auto [v, a, b] : e[u]) {
		if (!used[v]) {
			long long z = zhfs(v, u);
			bonus += b;
			bonus += z;
			ch.emplace_back(a - z - b, v);
		}
	}
	ans[1] = max(ans[1], bonus);
	used[u] = true; 
	{
		vector<pair<long long, int>> d;
		d.reserve(sz[u]);
		for (auto [v, a, b] : e[u]) {
			if (!used[v]) d.emplace_back(go(v, v, d) + a, v);
		}	
		sort(rbegin(d), rend(d));
		int f = -1;
		for (int i = 1; i < (int)d.size(); ++i) {
			if (d[i].second != d[0].second) {
				f = i;
				break;
			}
		}
		if (f != -1) {
			long long cur = 0;
			for (int i = 0; i < (int)d.size(); ++i) {
				cur += d[i].first;
				ans[i + 1 + (i < f)] = max(ans[i + 1 + (i < f)], cur + (i < f ? d[f].first : 0) + bonus);
			}
		}
	}
	for (auto [delta, v] : ch) {
		bonus += delta;
		solve(centroid(v, sz[v]), bonus);
		bonus -= delta;
	}
}

int main() {
	scanf("%d", &n);
	long long sum = 0;
	for (int i = 0; i < n - 1; ++i) {
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		--a, --b;
		e[a].emplace_back(b, c, d);
		e[b].emplace_back(a, d, c);
		sum += c;
		sum += d;
	}
	dfs(0);
	solve(centroid(0, n), 0);
	for (int i = 1; i <= n; ++i) {
		ans[i] = sum - ans[i];
	}
	for (int i = 2; i <= n; ++i) {
		ans[i] = min(ans[i], ans[i - 1]);
	}
	int q;
	scanf("%d", &q);
	while (q--) {
		int x;
		scanf("%d", &x);
		cout << ans[x] << "\n";
	}
	return 0;
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:110:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
designated_cities.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |   scanf("%d%d%d%d", &a, &b, &c, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:130:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
designated_cities.cpp:133:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |   scanf("%d", &x);
      |   ~~~~~^~~~~~~~~~

Subtask #1
0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 730 ms 16484 KB Output is correct
3 Correct 1067 ms 27836 KB Output is correct
4 Correct 717 ms 16468 KB Output is correct
5 Correct 312 ms 16588 KB Output is correct
6 Correct 856 ms 24636 KB Output is correct
7 Correct 250 ms 24832 KB Output is correct
8 Correct 1050 ms 33928 KB Output is correct
9 Correct 164 ms 28656 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 730 ms 16484 KB Output is correct
3 Correct 1067 ms 27836 KB Output is correct
4 Correct 717 ms 16468 KB Output is correct
5 Correct 312 ms 16588 KB Output is correct
6 Correct 856 ms 24636 KB Output is correct
7 Correct 250 ms 24832 KB Output is correct
8 Correct 1050 ms 33928 KB Output is correct
9 Correct 164 ms 28656 KB Output is correct
10 Incorrect 3 ms 4948 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

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