Submission #488451

#	Time	Username	Problem	Language	Result	Execution time	Memory
488451		denniskim	Biochips (IZhO12_biochips)	C++14	0 / 100	258 ms	524292 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][501];
ll rt;
ll q[200010][503];
priority_queue< pair<ll, ll> > pq;

void dfs(ll here, ll pa)
{
	for(ll i : vec[here])
	{
		if(i == pa)
			continue;
		
		dfs(i, here);
	}
	
	ll cc = 0;
	
	for(ll nx : vec[here])
	{
		if(nx == pa)
			continue;
		
		for(ll j = 1 ; j <= m ; j++)
		{
			if(dp[nx][j] == -1)
				break;
			
			q[nx][q[nx][502]++] = dp[nx][j] - dp[nx][j - 1];
		}
	}
	
	while(!pq.empty())
		pq.pop();
	
	for(ll i : vec[here])
	{
		if(q[i][502])
			pq.push(make_pair(q[i][0], i));
	}
	
	for(ll i = 1 ; i <= m ; i++)
	{
		if(pq.empty())
			break;
		
		pair<ll, ll> qq = pq.top();
		pq.pop();
		
		dp[here][i] = dp[here][i - 1] + qq.first;
		
		q[qq.second][501]++;
		
		if(q[qq.second][501] <= q[qq.second][502])
			pq.push(make_pair(q[qq.second][q[qq.second][501]], qq.second));
	}
	
	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] = q[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 'void dfs(ll, ll)':
biochips.cpp:31:5: warning: unused variable 'cc' [-Wunused-variable]
   31 |  ll cc = 0;
      |     ^~
biochips.cpp: In function 'int main()':
biochips.cpp:77:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
biochips.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |   scanf("%d %d", &all, &a[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100