# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
786230 | 2023-07-18T05:39:43 Z | 반딧불(#10026) | Paths (RMI21_paths) | C++17 | 600 ms | 12384 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n, k; vector<pair<int, ll> > link[100002]; multiset<ll> st[100002]; void add(multiset<ll> &A, multiset<ll> &B){ if(A.size() < B.size()) A.swap(B); for(int x: B){ A.insert(x); } B.clear(); while((int)A.size() > k) A.erase(A.begin()); } void dfs(int x, int p=-1){ if((int)link[x].size() - int(p!=-1) == 0){ st[x].insert(0); return; } for(auto y: link[x]){ if(y.first==p) continue; dfs(y.first, x); assert(!st[y.first].empty()); ll tmp = *st[y.first].rbegin(); st[y.first].erase(prev(st[y.first].end())); st[y.first].insert(tmp+y.second); add(st[x], st[y.first]); } // printf("Parent %d, x %d: ", p, x); // for(auto t: st[x]) printf("%lld ", t); // puts(""); } int main(){ scanf("%d %d", &n, &k); for(int i=1; i<n; i++){ int x, y; ll c; scanf("%d %d %lld", &x, &y, &c); link[x].push_back(make_pair(y, c)); link[y].push_back(make_pair(x, c)); } for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++) st[j].clear(); dfs(i); ll sum = 0; while((int)st[i].size() > k){ st[i].erase(st[i].begin()); } for(auto x: st[i]) sum+=x; printf("%lld\n", sum); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 7252 KB | Output is correct |
2 | Correct | 3 ms | 7252 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 7252 KB | Output is correct |
2 | Correct | 3 ms | 7252 KB | Output is correct |
3 | Incorrect | 8 ms | 7360 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 7252 KB | Output is correct |
2 | Correct | 3 ms | 7252 KB | Output is correct |
3 | Incorrect | 8 ms | 7360 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 7252 KB | Output is correct |
2 | Correct | 3 ms | 7252 KB | Output is correct |
3 | Incorrect | 8 ms | 7360 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1042 ms | 12384 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 7252 KB | Output is correct |
2 | Correct | 3 ms | 7252 KB | Output is correct |
3 | Incorrect | 8 ms | 7360 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |