8837 | 2024. 02. 01 10:38:52 | hackemon | Társaság (50) | cpp17 | Futási hiba 0/50 | 35ms | 65240 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 | 0/50 | ||||||
1 | Futási hiba | 0/0 | 29ms | 65240 KiB | |||
2 | Futási hiba | 0/0 | 29ms | 65004 KiB | |||
3 | Futási hiba | 0/3 | 30ms | 64772 KiB | |||
4 | Futási hiba | 0/3 | 30ms | 64516 KiB | |||
5 | Futási hiba | 0/3 | 29ms | 64280 KiB | |||
6 | Futási hiba | 0/3 | 29ms | 64172 KiB | |||
7 | Futási hiba | 0/3 | 29ms | 64160 KiB | |||
8 | Futási hiba | 0/3 | 30ms | 64128 KiB | |||
9 | Futási hiba | 0/3 | 29ms | 63912 KiB | |||
10 | Futási hiba | 0/3 | 35ms | 63676 KiB | |||
11 | Futási hiba | 0/3 | 34ms | 63436 KiB | |||
12 | Futási hiba | 0/3 | 26ms | 63432 KiB | |||
13 | Futási hiba | 0/4 | 35ms | 63312 KiB | |||
14 | Futási hiba | 0/4 | 28ms | 63176 KiB | |||
15 | Futási hiba | 0/4 | 28ms | 63172 KiB | |||
16 | Futási hiba | 0/4 | 29ms | 63160 KiB | |||
17 | Futási hiba | 0/4 | 29ms | 63156 KiB |