Submission #1276966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276966		SnowRaven52	Biochips (IZhO12_biochips)	C++20	0 / 100	25 ms	7628 KiB

biochips

#include <bits/stdc++.h>
using namespace std;

struct Res { double val; int cnt; };

int n, m;
vector<int> w, par;
vector<vector<int>> g;

double lam;

Res dfs(int v){
    double take = w[v] - lam;
    int cntT = 1;
    double skip = 0.0; int cntS = 0;
    for(int u : g[v]){
        Res r = dfs(u);
        skip += r.val;
        cntS += r.cnt;
    }
    if(take > skip) return {take, cntT};
    return {skip, cntS};
}

pair<double,int> solve(double L){
    lam = L;
    double val = 0.0; int cnt = 0;
    for(int i = 1; i <= n; i++) if(par[i] == 0){
        Res r = dfs(i);
        val += r.val; cnt += r.cnt;
    }
    return {val, cnt};
}

int main(){
    // freopen("main.in", "r", stdin);
	  // freopen(".out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    w.assign(n + 1, 0);
    par.assign(n + 1, 0);
    for(int i = 1; i <= n; i++) cin >> w[i];
    for(int i = 1; i <= n; i++) cin >> par[i];

    g.assign(n + 1, {});
    for(int i = 1; i <= n; i++) if(par[i] != 0) g[par[i]].push_back(i);

    double lo = -1e4, hi = 1e4;
    for(int it = 0; it < 70; it++){
        double mid = (lo + hi) * 0.5;
        auto [val, cnt] = solve(mid);
        if(cnt >= m) lo = mid; else hi = mid;
    }
    auto [val, cnt] = solve(lo);
    long long ans = llround(val + lo * m);
    cout << ans << endl;
}

• Subtask 1: 0 / 100