8838 | 2024. 02. 01 10:39:15 | hackemon | Társaság (50) | cpp17 | Elfogadva 50/50 | 14ms | 4276 KiB |
#include <bits/stdc++.h>
using namespace std;
int counter = 0;
long long mid = 0;
vector<vector<pair<long long, long long>>> adj;
long long bejaras(int start) {
long long maxi = 0;
for(int i = 0;i <adj[start].size();i++ ) {
long long val = bejaras(adj[start][i].first) + adj[start][i].second;
if(val > mid) {
val = 0;
counter++;
}
maxi = max(maxi, val);
}
return maxi;
}
void solve() {
//freopen("be2.txt", "r", stdin);
int n, k;
cin >> n >> k;
adj.resize(n+1);
for(int i = 2;i <= n;i++) {
long long a, b;
cin >> a >> b;
adj[a].push_back({i, b});
}
long long l = 0, r = 1e13;
//use a binary search to estimate the result
while(l < r) {
mid = (l + r)/2;
bejaras(1);
if(counter <= k) {
r = mid;
} else {
if(l + 1 == r) break;
l = mid;
}
counter = 0;
}
cout << r << endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
while(t-- ) {
solve();
}
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1892 KiB | |||
2 | Elfogadva | 0/0 | 8ms | 2456 KiB | |||
3 | Elfogadva | 3/3 | 3ms | 2184 KiB | |||
4 | Elfogadva | 3/3 | 3ms | 2396 KiB | |||
5 | Elfogadva | 3/3 | 3ms | 2608 KiB | |||
6 | Elfogadva | 3/3 | 3ms | 2832 KiB | |||
7 | Elfogadva | 3/3 | 3ms | 2932 KiB | |||
8 | Elfogadva | 3/3 | 3ms | 3052 KiB | |||
9 | Elfogadva | 3/3 | 4ms | 3376 KiB | |||
10 | Elfogadva | 3/3 | 6ms | 3504 KiB | |||
11 | Elfogadva | 3/3 | 6ms | 3448 KiB | |||
12 | Elfogadva | 3/3 | 8ms | 3620 KiB | |||
13 | Elfogadva | 4/4 | 9ms | 3900 KiB | |||
14 | Elfogadva | 4/4 | 9ms | 3896 KiB | |||
15 | Elfogadva | 4/4 | 10ms | 4024 KiB | |||
16 | Elfogadva | 4/4 | 13ms | 4024 KiB | |||
17 | Elfogadva | 4/4 | 14ms | 4276 KiB |