# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
871080 |
2023-11-09T20:44:44 Z |
MinaRagy06 |
Paths (RMI21_paths) |
C++17 |
|
600 ms |
277096 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 100'005;
multiset<ll> s[N];
vector<array<int, 2>> adj[N];
void dfs(int i, int par, int parc) {
for (auto [nxt, w] : adj[i]) {
if (nxt == par) continue;
dfs(nxt, i, w);
if (s[i] < s[nxt]) {
swap(s[i], s[nxt]);
}
for (auto j : s[nxt]) {
s[i].insert(j);
}
}
if (adj[i].size() == 1) s[i].insert(0);
ll val = *s[i].begin();
s[i].erase(s[i].begin());
s[i].insert(val - parc);
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n, k;
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++) {
s[j].clear();
}
dfs(i, 0, 0);
ll sum = 0;
int cnt = 0;
for (auto j : s[i]) {
if (cnt == k) break;
sum += j;
cnt++;
}
cout << -sum << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7260 KB |
Output is correct |
2 |
Correct |
2 ms |
7256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7260 KB |
Output is correct |
2 |
Correct |
2 ms |
7256 KB |
Output is correct |
3 |
Correct |
19 ms |
7512 KB |
Output is correct |
4 |
Correct |
20 ms |
7644 KB |
Output is correct |
5 |
Correct |
58 ms |
7772 KB |
Output is correct |
6 |
Correct |
5 ms |
7516 KB |
Output is correct |
7 |
Correct |
12 ms |
7516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7260 KB |
Output is correct |
2 |
Correct |
2 ms |
7256 KB |
Output is correct |
3 |
Correct |
19 ms |
7512 KB |
Output is correct |
4 |
Correct |
20 ms |
7644 KB |
Output is correct |
5 |
Correct |
58 ms |
7772 KB |
Output is correct |
6 |
Correct |
5 ms |
7516 KB |
Output is correct |
7 |
Correct |
12 ms |
7516 KB |
Output is correct |
8 |
Execution timed out |
1041 ms |
8436 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7260 KB |
Output is correct |
2 |
Correct |
2 ms |
7256 KB |
Output is correct |
3 |
Correct |
19 ms |
7512 KB |
Output is correct |
4 |
Correct |
20 ms |
7644 KB |
Output is correct |
5 |
Correct |
58 ms |
7772 KB |
Output is correct |
6 |
Correct |
5 ms |
7516 KB |
Output is correct |
7 |
Correct |
12 ms |
7516 KB |
Output is correct |
8 |
Execution timed out |
1041 ms |
8436 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1018 ms |
277096 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7260 KB |
Output is correct |
2 |
Correct |
2 ms |
7256 KB |
Output is correct |
3 |
Correct |
19 ms |
7512 KB |
Output is correct |
4 |
Correct |
20 ms |
7644 KB |
Output is correct |
5 |
Correct |
58 ms |
7772 KB |
Output is correct |
6 |
Correct |
5 ms |
7516 KB |
Output is correct |
7 |
Correct |
12 ms |
7516 KB |
Output is correct |
8 |
Execution timed out |
1041 ms |
8436 KB |
Time limit exceeded |
9 |
Halted |
0 ms |
0 KB |
- |