제출 #1259258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1259258		wheatley	바이오칩 (IZhO12_biochips)	C++20	80 / 100	745 ms	589824 KiB

biochips

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NEG = LLONG_MIN/4;

int N, M;
vector<vector<int>> g;
vector<int> mem;
vector<int> tin, tout;
int timer = 0;

void dfs(int u) {
    tin[u] = ++timer;
    for (int v : g[u]) dfs(v);
    tout[u] = timer;
}

struct Node {
    int id;
    int l, r; 
    int w;    
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;
    g.assign(N, {});
    mem.resize(N);
    vector<int> parent(N,-1), roots;
    for (int i=0;i<N;i++) {
        int p,x; cin >> p >> x;
        mem[i]=x;
        if(p==0) roots.push_back(i);
        else { p--; g[p].push_back(i); parent[i]=p; }
    }

    tin.resize(N); tout.resize(N);
    for(int r:roots) dfs(r);

    vector<Node> nodes(N);
    for(int i=0;i<N;i++) nodes[i] = {i, tin[i], tout[i], mem[i]};
    sort(nodes.begin(), nodes.end(), [](auto &a, auto &b){
        return a.r < b.r;
    });

    vector<int> prev(N);
    vector<int> ends(N);
    for(int i=0;i<N;i++) ends[i]=nodes[i].r;
    for(int i=0;i<N;i++){
        int L = nodes[i].l;
        int j = int(upper_bound(ends.begin(), ends.end(), L-1) - ends.begin()) - 1;
        prev[i] = j; 
    }

    vector<vector<ll>> dp(M+1, vector<ll>(N, NEG));

    for(int i=0;i<N;i++) dp[0][i]=0;

    for(int i=0;i<N;i++){
        for(int k=1;k<=M;k++){

            dp[k][i] = (i>0 ? dp[k][i-1] : NEG);

            ll cand = (nodes[i].w) + (prev[i]>=0 ? dp[k-1][prev[i]] : (k==1?0:NEG));
            dp[k][i] = max(dp[k][i], cand);
        }
    }

    cout << dp[M][N-1] << "\n";
}

• Subtask 1: 80 / 100