Submission #488452

#	Time	Username	Problem	Language	Result	Execution time	Memory
488452		denniskim	Biochips (IZhO12_biochips)	C++14	100 / 100	251 ms	411840 KiB

biochips

#include <bits/stdc++.h>

using namespace std;
typedef int ll;
typedef long double ld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second

ll n, m;
ll a[200010];
ll all;
vector<ll> vec[200010];
ll dp[200010][510];
ll rt;
priority_queue< pair< pair<ll, ll>, ll> > pq;

void dfs(ll here, ll pa)
{
	for(ll i : vec[here])
	{
		if(i == pa)
			continue;
		
		dfs(i, here);
	}
	
	while(!pq.empty())
		pq.pop();
	
	for(ll i : vec[here])
	{
		if(i == pa)
			continue;
		
		if(dp[i][1] != -1)
			pq.push(make_pair(make_pair(dp[i][1] - dp[i][0], i), 1));
	}
	
	for(ll i = 1 ; i <= m ; i++)
	{
		if(pq.empty())
			break;
		
		pair< pair<ll, ll>, ll> qq = pq.top();
		pq.pop();
		
		dp[here][i] = dp[here][i - 1] + qq.first.first;
		
		if(dp[qq.first.second][qq.second + 1] != -1)
			pq.push(make_pair(make_pair(dp[qq.first.second][qq.second + 1] - dp[qq.first.second][qq.second], qq.first.second), qq.second + 1));
	}
	
	dp[here][1] = max(dp[here][1], a[here]);
}

int main(void)
{
	scanf("%d %d", &n, &m);
	
	for(ll i = 1 ; i <= n ; i++)
	{
		scanf("%d %d", &all, &a[i]);
		
		if(!all)
			rt = i;
		
		else
		{
			vec[i].push_back(all);
			vec[all].push_back(i);
		}
	}
	
	for(ll i = 1 ; i <= n ; i++)
	{
		for(ll j = 1 ; j <= m ; j++)
			dp[i][j] = -1;
	}
	
	dfs(rt, 0);
	dp[rt][1] = max(dp[rt][1], a[rt]);
	
	printf("%d", dp[rt][m]);
	return 0;
}

Compilation message (stderr)

biochips.cpp: In function 'int main()':
biochips.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
biochips.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   scanf("%d %d", &all, &a[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100