8835 | 2024. 02. 01 10:36:27 | hackemon | Társaság (50) | cpp17 | Hibás válasz 7/50 | 4ms | 3852 KiB |
#include <bits/stdc++.h>
using namespace std;
int counter = 0;
long long mid = 0;
vector<vector<pair<int, int>>> 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++) {
int 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 | 7/50 | ||||||
1 | Hibás válasz | 0/0 | 4ms | 2276 KiB | |||
2 | Hibás válasz | 0/0 | 4ms | 2548 KiB | |||
3 | Hibás válasz | 0/3 | 4ms | 2760 KiB | |||
4 | Hibás válasz | 0/3 | 4ms | 2908 KiB | |||
5 | Elfogadva | 3/3 | 4ms | 3008 KiB | |||
6 | Hibás válasz | 0/3 | 4ms | 2968 KiB | |||
7 | Hibás válasz | 0/3 | 4ms | 3112 KiB | |||
8 | Hibás válasz | 0/3 | 4ms | 3324 KiB | |||
9 | Hibás válasz | 0/3 | 4ms | 3280 KiB | |||
10 | Hibás válasz | 0/3 | 4ms | 3412 KiB | |||
11 | Hibás válasz | 0/3 | 4ms | 3384 KiB | |||
12 | Hibás válasz | 0/3 | 4ms | 3392 KiB | |||
13 | Hibás válasz | 0/4 | 4ms | 3388 KiB | |||
14 | Hibás válasz | 0/4 | 4ms | 3388 KiB | |||
15 | Hibás válasz | 0/4 | 4ms | 3412 KiB | |||
16 | Elfogadva | 4/4 | 4ms | 3652 KiB | |||
17 | Hibás válasz | 0/4 | 4ms | 3852 KiB |