#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;
int n, k;
vector <int> E[200050];
int p[200050], C[200050];
int down[200050], del[200050];
void pre(int x) {
down[x] = C[x];
for(int e : E[x]) {
pre(e);
if(down[e] >= C[x]) del[x] = 1;
down[x] = max(down[x], down[e]);
}
}
void del_dfs(int x) {
if(del[x]) {
for(int e : E[x]) p[e] = p[x];
p[x] = -1;
}
for(int e : E[x]) del_dfs(e);
}
int state[200050];
void solve(){
int r = -1;
scanf("%d%d", &n, &k);
for(int i=1;i<=n;i++) {
scanf("%d%d", p+i, C+i);
if(p[i] == 0) r = i;
else E[p[i]].pb(i);
}
pre(r);
del_dfs(r);
for(int i=1;i<=n;i++) E[i].clear();
for(int i=1;i<=n;i++) if(p[i] != -1) E[p[i]].pb(i);
for(int i=1;i<=n;i++) sort(all(E[i]), [](int a, int b) { return C[a] > C[b];});
priority_queue <pii> pq;
for(int e : E[0]) pq.push(pii(C[e], e));
int cnt = 0, ans = 0;
while(!pq.empty()) {
pii t = pq.top(); pq.pop();
ans += t.Fi; ++cnt;
if(cnt == k) break;
int u = t.Se;
if(state[u] == 0) {
if(sz(E[u]) <= 1) continue;
pq.push(pii(C[E[u][0]] + C[E[u][1]] - t.Fi, u));
state[u] = 1;
}
else {
rep(v, 2) {
int a = E[u][v];
state[a] = 1;
if(sz(E[a]) <= 1) continue;
pq.push(pii(C[E[a][0]] + C[E[a][1]] - C[a], a));
}
for(int i=2;i<sz(E[u]);i++) pq.push(pii(C[E[u][i]], E[u][i]));
}
}
printf("%d\n", ans);
}
int main(){
int Tc = 1; // scanf("%d\n", &Tc);
for(int tc=1;tc<=Tc;tc++){
//printf("Case #%d\n", tc);
solve();
}
return 0;
};
Compilation message
biochips.cpp: In function 'void solve()':
biochips.cpp:59:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &k);
^
biochips.cpp:61:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", p+i, C+i);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
10616 KB |
Output is correct |
| 2 |
Correct |
0 ms |
10616 KB |
Output is correct |
| 3 |
Correct |
0 ms |
10616 KB |
Output is correct |
| 4 |
Correct |
0 ms |
10892 KB |
Output is correct |
| 5 |
Correct |
3 ms |
10892 KB |
Output is correct |
| 6 |
Correct |
6 ms |
10892 KB |
Output is correct |
| 7 |
Correct |
56 ms |
15872 KB |
Output is correct |
| 8 |
Correct |
63 ms |
15884 KB |
Output is correct |
| 9 |
Correct |
66 ms |
15824 KB |
Output is correct |
| 10 |
Correct |
59 ms |
15824 KB |
Output is correct |
