oj.uz

답안 #871099

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
871099 2023-11-09T21:57:51 Z MinaRagy06 Paths (RMI21_paths) C++17
0 / 100
 600 ms 15228 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] == dp[nxt][0]) 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
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 7260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 7260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 7260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 7260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1010 ms 15228 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 7260 KB Output isn't correct
2 Halted 0 ms 0 KB -