oj.uz

Submission #871100

# Submission time Handle Problem Language Result Execution time Memory
871100 2023-11-09T22:01:01 Z MinaRagy06 Paths (RMI21_paths) C++17
56 / 100
 600 ms 13096 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 100'005;
vector<array<int, 2>> adj[N];
int n, k;
ll vals[N];
pair<ll, int> dp[N][2];
void dfs(int i, int par, int parc) {
	dp[i][0] = dp[i][1] = {-1e18, 0};
	for (auto [nxt, w] : adj[i]) {
		if (nxt == par) continue;
		dfs(nxt, i, w);
		pair<ll, int> nxtval = dp[nxt][0];
		nxtval.first += w;
		if (nxtval > dp[i][1]) {
			dp[i][1] = nxtval;
		}
		if (dp[i][0] < dp[i][1]) {
			swap(dp[i][0], dp[i][1]);
		}
	}
	if (adj[i].size() == 1) {
		dp[i][0] = {0, i};
	}
	vals[dp[i][0].second] += parc;
}
ll ans[N];
ll calc() {
	vector<ll> cur;
	for (int i = 1; i <= n; i++) {
		cur.push_back(vals[i]);
	}
	sort(cur.rbegin(), cur.rend());
	ll sum = 0;
	for (int i = 0; i < k; i++) {
		sum += cur[i];
	}
	return sum;
}
void dfs2(int i, int par, int parc, pair<ll, int> dpup) {
	dpup.first += parc;
	vals[dp[i][0].second] -= parc;
	ans[i] = calc();
	for (auto [nxt, w] : adj[i]) {
		if (nxt == par) continue;
		pair<ll, int> mx = dp[i][0];
		if (dp[i][0].second == dp[nxt][0].second) mx = dp[i][1];
		mx = max(mx, dpup);
		vals[mx.second] += w;
		dfs2(nxt, i, w, mx);
		vals[mx.second] -= w;
	}
	vals[dp[i][0].second] += parc;
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k;
	for (int i = 1, u, v, w; i < n; i++) {
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	dfs(1, 0, 0);
	dfs2(1, 0, 0, {0, 0});
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7324 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7324 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7324 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7324 KB Output is correct
8 Correct 20 ms 7260 KB Output is correct
9 Correct 13 ms 7456 KB Output is correct
10 Correct 9 ms 7260 KB Output is correct
11 Correct 24 ms 7656 KB Output is correct
12 Correct 12 ms 7516 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7324 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7324 KB Output is correct
8 Correct 20 ms 7260 KB Output is correct
9 Correct 13 ms 7456 KB Output is correct
10 Correct 9 ms 7260 KB Output is correct
11 Correct 24 ms 7656 KB Output is correct
12 Correct 12 ms 7516 KB Output is correct
13 Correct 102 ms 7468 KB Output is correct
14 Correct 57 ms 7568 KB Output is correct
15 Correct 30 ms 7492 KB Output is correct
16 Correct 115 ms 7480 KB Output is correct
17 Correct 54 ms 7728 KB Output is correct
18 Correct 45 ms 7480 KB Output is correct
19 Correct 98 ms 7472 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1024 ms 13096 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7256 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7324 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 2 ms 7260 KB Output is correct
7 Correct 2 ms 7324 KB Output is correct
8 Correct 20 ms 7260 KB Output is correct
9 Correct 13 ms 7456 KB Output is correct
10 Correct 9 ms 7260 KB Output is correct
11 Correct 24 ms 7656 KB Output is correct
12 Correct 12 ms 7516 KB Output is correct
13 Correct 102 ms 7468 KB Output is correct
14 Correct 57 ms 7568 KB Output is correct
15 Correct 30 ms 7492 KB Output is correct
16 Correct 115 ms 7480 KB Output is correct
17 Correct 54 ms 7728 KB Output is correct
18 Correct 45 ms 7480 KB Output is correct
19 Correct 98 ms 7472 KB Output is correct
20 Execution timed out 1024 ms 13096 KB Time limit exceeded
21 Halted 0 ms 0 KB -