Submission #333851

#	Time	Username	Problem	Language	Result	Execution time	Memory
333851		limabeans	Biochips (IZhO12_biochips)	C++17	0 / 100	314 ms	524292 KiB

biochips

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl











const int maxn = 5e5+10;


int n,m;
vector<int> g[maxn];
int a[maxn];

int cloc = 0;
int tin[maxn];
int arr[maxn];
int tout[maxn];

void dfs(int at, int p) {

    assert(cloc<maxn);
    
    arr[cloc] = at;
    tin[at] = cloc;
    cloc++;
    
    for (int to: g[at]) {
	if (to == p) continue;
	dfs(to, at);
    }

    tout[at] = cloc;
}


void setmax(int &x, int y) {
    x = max(x, y);
}

int dp[512][maxn];


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>m;
    int r=-1;
    for (int i=1; i<=n; i++) {
	int p;
	cin>>p;
	if (p==0) {
	    r=i;
	} else {
	    g[p].push_back(i);
	}
	cin>>a[i];
    }


    dfs(r,-1);




    for (int i=0; i<512; i++) {
	for (int j=0; j<maxn; j++) {
	    dp[i][j] = -1e9;
	}
    }

    
    dp[0][0] = 0;


    for (int j=0; j<=m; j++) {
	for (int i=0; i<cloc; i++) {

	    int ptr = tout[arr[i]];
	    if (j<m) {
		setmax(dp[j+1][ptr], dp[j][i]+a[arr[i]]);
	    }
	    setmax(dp[j][i+1], dp[j][i]);
	}
    }

    cout<<dp[m][cloc]<<endl;
    
    return 0;
}

• Subtask 1: 0 / 100