oj.uz

Submission #954382

# Submission time Handle Problem Language Result Execution time Memory
954382 2024-03-27T18:07:49 Z TAhmed33 Paths (RMI21_paths) C++
56 / 100
 600 ms 15232 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 25;
vector <pair <int, ll>> adj[MAXN];
pair <ll, ll> dp[MAXN], dq[MAXN];
ll edge[MAXN];
int n, k;
void dfs (int pos, int par) {
	if ((int)adj[pos].size() == 1) {
		dp[pos] = {edge[pos], pos};
		return;
	}
	for (auto j : adj[pos]) {
		if (j.first == par) continue;
		edge[j.first] = j.second;
		dfs(j.first, pos);
		dp[pos] = max(dp[pos], dp[j.first]);
	}
	dp[pos].first += edge[pos];
}
void dfs2 (int pos, int par, pair <ll, ll> x = {}) {
	x.first += edge[pos];
	dq[pos] = x;
	deque <pair <ll, ll>> u;
	for (auto j : adj[pos]) {
		if (j.first == par) continue;
		u.push_back(dp[j.first]);
	}
	for (int i = (int)u.size() - 2; i >= 0; i--) u[i] = max(u[i], u[i + 1]);
	for (auto j : adj[pos]) {
		if (j.first == par) continue;
		u.pop_front();
		auto g = x; if (!u.empty()) g = max(g, u.front());
		dfs2(j.first, pos, g);
		x = max(x, dp[j.first]);
	}
}
struct DS {
	ll val[MAXN];
	void upd (int a, ll b) {
		val[a] += b;
	}
	ll get () {
		vector <ll> d;
		for (int i = 1; i <= n; i++) d.push_back(val[i]);
		sort(d.begin(), d.end());
		reverse(d.begin(), d.end());
		ll sum = 0;
		for (int i = 0; i < k; i++) sum += d[i];
		return sum;
	}
} cur;
ll ans[MAXN];
void dfs3 (int pos, int par) {
	if (par != -1) {
		cur.upd(dp[pos].second, -edge[pos]);
		cur.upd(dq[pos].second, edge[pos]);
	}
	ans[pos] = cur.get();
	for (auto j : adj[pos]) {
		if (j.first != par) {
			dfs3(j.first, pos);
		}
	}
	if (par != -1) {
		cur.upd(dq[pos].second, -edge[pos]);
		cur.upd(dp[pos].second, edge[pos]);
	}
}
int main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	if (n == 1) {
		cout << "0\n";
		return 0;
	}
	if (n == 2) {
		int a, b, c; cin >> a >> b >> c;
		cout << c << '\n' << c << '\n';
		return 0;
	}
	for (int i = 1; i < n; i++) {
		int a, b, c; cin >> a >> b >> c;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}
	int root = -1;
	for (int i = 1; i <= n; i++) {
		if ((int)adj[i].size() >= 2) root = i;
	}
	dfs(root, -1);
	dfs2(root, -1);
	for (int i = 1; i <= n; i++) {
		if (i != root) {
			cur.upd(dp[i].second, edge[i]);
		}
	}
	dfs3(root, -1);
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << '\n';
	}
}

Subtask #1
8.0 / 8.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 4 ms 8028 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 8104 KB Output is correct
6 Correct 3 ms 8028 KB Output is correct
7 Correct 3 ms 8028 KB Output is correct
8 Correct 26 ms 8200 KB Output is correct
9 Correct 16 ms 8540 KB Output is correct
10 Correct 12 ms 8284 KB Output is correct
11 Correct 26 ms 8024 KB Output is correct
12 Correct 15 ms 8028 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 4 ms 8028 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 8104 KB Output is correct
6 Correct 3 ms 8028 KB Output is correct
7 Correct 3 ms 8028 KB Output is correct
8 Correct 26 ms 8200 KB Output is correct
9 Correct 16 ms 8540 KB Output is correct
10 Correct 12 ms 8284 KB Output is correct
11 Correct 26 ms 8024 KB Output is correct
12 Correct 15 ms 8028 KB Output is correct
13 Correct 114 ms 8280 KB Output is correct
14 Correct 67 ms 9040 KB Output is correct
15 Correct 41 ms 8280 KB Output is correct
16 Correct 119 ms 8304 KB Output is correct
17 Correct 60 ms 8316 KB Output is correct
18 Correct 52 ms 8536 KB Output is correct
19 Correct 108 ms 8284 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 15232 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 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 4 ms 8028 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 8104 KB Output is correct
6 Correct 3 ms 8028 KB Output is correct
7 Correct 3 ms 8028 KB Output is correct
8 Correct 26 ms 8200 KB Output is correct
9 Correct 16 ms 8540 KB Output is correct
10 Correct 12 ms 8284 KB Output is correct
11 Correct 26 ms 8024 KB Output is correct
12 Correct 15 ms 8028 KB Output is correct
13 Correct 114 ms 8280 KB Output is correct
14 Correct 67 ms 9040 KB Output is correct
15 Correct 41 ms 8280 KB Output is correct
16 Correct 119 ms 8304 KB Output is correct
17 Correct 60 ms 8316 KB Output is correct
18 Correct 52 ms 8536 KB Output is correct
19 Correct 108 ms 8284 KB Output is correct
20 Execution timed out 1076 ms 15232 KB Time limit exceeded
21 Halted 0 ms 0 KB -