# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
31984 | cki86201 | Biochips (IZhO12_biochips) | C++11 | 66 ms | 15884 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |