Submission #954359

#	Time	Username	Problem	Language	Result	Execution time	Memory
954359		starchan	Biochips (IZhO12_biochips)	C++17	30 / 100	482 ms	400544 KiB

biochips

#include<bits/stdc++.h>
using namespace std;
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
const int MX = 2e5+5, SMX = 5e2+2;
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
vector<int> adj[MX];
int dp[MX][SMX];
int chungus[SMX];//initialised with zero.
vector<int> w;
vector<int> euler;
int timer;
vector<int> tin;
int m;
vector<int> tout;
void dfs(int u)
{
	euler.pb(u);
	tin[u] = timer++;
	for(int v: adj[u])
	{
		dfs(v);
		for(int i = 1; i <= m; i++)
			chungus[i] = max(chungus[i], dp[tin[v]][i]);
	}
	for(int i = 1; i <= m; i++)
		dp[tin[u]][i] = max(((tin[u] > 0) ? dp[tin[u]-1][i] : 0), w[u] + chungus[i-1]);
	return;
}
signed main()
{
	fast();
	//freopen("d.in", "r", stdin);
	//freopen("d.out", "w", stdout);
	int n;
	cin >> n >> m;
	w.resize(n+1);
	tin.resize(n+1);
	int root = -1;
	for(int i = 1; i <= n; i++)
	{
		int x; cin >> x >> w[i];
		if(x)
			adj[x].pb(i);
		else
			root = i;
	}
	dfs(root);
	cout << dp[n-1][m] << "\n";
	return 0;
}	

• Subtask 1: 30 / 100