답안 #871091

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
871091	2023-11-09T21:08:25 Z	MinaRagy06	Paths (RMI21_paths)	C++17	56 / 100	600 ms	7240 KB

Main

#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> dfs(int i, int par, int parc) {
	pair<ll, int> mx = {-1e18, 0};
	for (auto [nxt, w] : adj[i]) {
		if (nxt == par) continue;
		mx = max(mx, dfs(nxt, i, w));
	}
	if (adj[i].size() == 1) {
		vals[i] = parc;
		return {parc, i};
	}
	vals[mx.second] += parc;
	mx.first += parc;
	return mx;
}
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});
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			vals[j] = 0;
		}
		dfs(i, 0, 0);
		sort(vals + 1, vals + n + 1);
		reverse(vals + 1, vals + n + 1);
		ll sum = 0;
		for (int j = 1; j <= k; j++) {
			sum += vals[j];
		}
		cout << sum << '\n';
	}
	return 0;
}

Subtask #1

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	3416 KB	Output is correct
2	Correct	1 ms	3160 KB	Output is correct

Subtask #2

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	3416 KB	Output is correct
2	Correct	1 ms	3160 KB	Output is correct
3	Correct	2 ms	3420 KB	Output is correct
4	Correct	2 ms	3420 KB	Output is correct
5	Correct	2 ms	3420 KB	Output is correct
6	Correct	2 ms	3420 KB	Output is correct
7	Correct	2 ms	3420 KB	Output is correct

Subtask #3

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	3416 KB	Output is correct
2	Correct	1 ms	3160 KB	Output is correct
3	Correct	2 ms	3420 KB	Output is correct
4	Correct	2 ms	3420 KB	Output is correct
5	Correct	2 ms	3420 KB	Output is correct
6	Correct	2 ms	3420 KB	Output is correct
7	Correct	2 ms	3420 KB	Output is correct
8	Correct	28 ms	3420 KB	Output is correct
9	Correct	21 ms	3416 KB	Output is correct
10	Correct	17 ms	3420 KB	Output is correct
11	Correct	29 ms	3420 KB	Output is correct
12	Correct	19 ms	3460 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	3416 KB	Output is correct
2	Correct	1 ms	3160 KB	Output is correct
3	Correct	2 ms	3420 KB	Output is correct
4	Correct	2 ms	3420 KB	Output is correct
5	Correct	2 ms	3420 KB	Output is correct
6	Correct	2 ms	3420 KB	Output is correct
7	Correct	2 ms	3420 KB	Output is correct
8	Correct	28 ms	3420 KB	Output is correct
9	Correct	21 ms	3416 KB	Output is correct
10	Correct	17 ms	3420 KB	Output is correct
11	Correct	29 ms	3420 KB	Output is correct
12	Correct	19 ms	3460 KB	Output is correct
13	Correct	160 ms	3492 KB	Output is correct
14	Correct	119 ms	3672 KB	Output is correct
15	Correct	73 ms	3416 KB	Output is correct
16	Correct	154 ms	3528 KB	Output is correct
17	Correct	93 ms	3532 KB	Output is correct
18	Correct	75 ms	3680 KB	Output is correct
19	Correct	148 ms	3548 KB	Output is correct

Subtask #5

0 / 12.0

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

Subtask #6

0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	3416 KB	Output is correct
2	Correct	1 ms	3160 KB	Output is correct
3	Correct	2 ms	3420 KB	Output is correct
4	Correct	2 ms	3420 KB	Output is correct
5	Correct	2 ms	3420 KB	Output is correct
6	Correct	2 ms	3420 KB	Output is correct
7	Correct	2 ms	3420 KB	Output is correct
8	Correct	28 ms	3420 KB	Output is correct
9	Correct	21 ms	3416 KB	Output is correct
10	Correct	17 ms	3420 KB	Output is correct
11	Correct	29 ms	3420 KB	Output is correct
12	Correct	19 ms	3460 KB	Output is correct
13	Correct	160 ms	3492 KB	Output is correct
14	Correct	119 ms	3672 KB	Output is correct
15	Correct	73 ms	3416 KB	Output is correct
16	Correct	154 ms	3528 KB	Output is correct
17	Correct	93 ms	3532 KB	Output is correct
18	Correct	75 ms	3680 KB	Output is correct
19	Correct	148 ms	3548 KB	Output is correct
20	Execution timed out	1064 ms	7240 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-