제출 #1206843

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206843		em4ma2	바이오칩 (IZhO12_biochips)	C++20	0 / 100	199 ms	401712 KiB

biochips

//                                 اللهم صل على محمد وعلى ال محمد كما صليت على ابراهيم وعلى ال ابراهيم انك حميد مجيد
#include "bits/stdc++.h"

using namespace std;

#define ll long long
//#define int long long
#define pb push_back
#define applejuice ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

//const int mod=1e9+7;
const int mod=998244353;
const ll inf=1e17;
const int mxsz=2e5+4;
const int off=1<<20;
const int siz=504;

vector<int>adj[mxsz];
int vis[mxsz];
int a[mxsz];
int mx=0;
int dp[mxsz][siz];
int sz[mxsz];
vector<int>res(mxsz);

void dfs(int i){
    vis[i]=1;
    for (auto x:adj[i]){
        if (!vis[x]){
            dfs(x);
            sz[i]+=sz[x];
        }
    }
}

void tra(int i,int m){
    vis[i]=1;
    if (adj[i].size()>1) {
        for (int km = 1; km < adj[i].size(); km++) {
            auto x = adj[i][km], y = adj[i][km - 1];
            if (!vis[x]) {
                fill(res.begin(), res.end(), 0);
                for (int j = 1; j <= sz[x]; j++) {
                    for (int l = 1; l <= sz[y]; l++) {
                        res[i + j] = max(res[i + j], a[i] + a[j]);
                    }
                }
                dp[i][m] = res[m];
                dfs(x);
            }
        }
    }else{
        for (auto x:adj[i]){
            if (!vis[x]){
                dp[i][m]=max(dp[x][m],a[i]);
                dfs(x);
            }
        }
    }
}

signed main(){
    applejuice;

    int n,m;
    cin>>n>>m;
    int root;
    for (int i=1;i<=n;i++){
        int p, x;
        cin>>p>>x;
        a[i]=x;
        if (p==0)root=i;
        adj[p].pb(i);
    }
    for (int i=0;i<=n;i++){
        for (int j=0;j<=m;j++){
            dp[i][j]=-1;
        }
    }
    int abs=0,sum;
    for (int i=1;i<=n;i++){
        if (adj[i].size()==0){
            dp[i][1]=a[i];
        }
    }
    for (int i=1;i<=n;i++){
        sz[i]=1;
    }
    dfs(root);
    for (int i=1;i<=n;i++)vis[i]=0;
    tra(root,m);
    cout<<dp[root][m]<<endl;

}

• Subtask 1: 0 / 100