#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define oo 1e9
#define pii pair<int, int>
const int MAX = 2002;
int n, k;
pii segTree[4 * MAX];
int lazy[4 * MAX];
vector<pii> g[MAX];
int timeIn[MAX], timeOut[MAX], pathVal[MAX], rtimeIn[MAX];
bool marked[MAX];
pii par[MAX];
void relax(int node, int l, int r){
if(lazy[node] == 0) return;
segTree[node].first += lazy[node];
if(l != r){
lazy[2 * node] += lazy[node];
lazy[2 * node + 1] += lazy[node];
}
lazy[node] = 0;
}
void build(int node, int l, int r){
if(l == r){
segTree[node] = {pathVal[rtimeIn[l]], rtimeIn[l]};
return;
}
int mid = (l + r) / 2;
build(2 * node, l, mid);
build(2 * node + 1, mid + 1, r);
segTree[node] = max(segTree[2 * node], segTree[2 * node + 1]);
}
void update(int node, int l, int r, int ul, int ur, int val){
relax(node, l, r);
if(ul > r || l > ur) return;
if(ul <= l && r <= ur){
lazy[node] += val;
relax(node, l, r);
return;
}
int mid = (l + r) / 2;
update(2 * node, l, mid, ul, ur, val);
update(2 * node + 1, mid + 1, r, ul, ur, val);
segTree[node] = max(segTree[2 * node], segTree[2 * node + 1]);
}
pii ask(int node, int l, int r, int ql, int qr){
relax(node, l, r);
if(ql > r || l > qr) return {0, 0};
if(ql <= l && r <= qr){
return segTree[node];
}
int mid = (l + r) / 2;
return max(ask(2 * node, l, mid, ql, qr), ask(2 * node + 1, mid + 1, r, ql, qr));
}
int t = 0;
void dfs(int node, int p, int h){
timeIn[node] = ++t;
rtimeIn[t] = node;
pathVal[node] = h;
for(pii to : g[node]){
if(p == to.first) continue;
par[to.first] = make_pair(node, to.second);
dfs(to.first, node, h + to.second);
}
timeOut[node] = t;
}
int main(){
cin >> n >> k;
for(int i = 1; i < n; i++){
int u, v, a; cin >> u >> v >> a;
g[u].push_back({v, a});
g[v].push_back({u, a});
}
for(int i = 1; i <= n; i++){
t = 0;
memset(segTree, 0, sizeof(segTree));
memset(lazy, 0, sizeof(lazy));
memset(marked, 0, sizeof(marked));
dfs(i, i, 0);
build(1, 1, n);
int ans = 0;
for(int j = 0; j < k; j++){
pii m = ask(1, 1, n, 1, n);
if(m.first == 0) break;
ans += m.first;
int a = m.second;
while(a != i){
if(marked[a]) break;
update(1, 1, n, timeIn[a], timeOut[a], -par[a].second);
marked[a] = true;
a = par[a].first;
}
}
cout << ans << '\n';
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:88:43: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<int, int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
88 | memset(segTree, 0, sizeof(segTree));
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from Main.cpp:2:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<int, int>' declared here
211 | struct pair
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
