oj.uz

Submission #488452

# Submission time Handle Problem Language Result Execution time Memory
488452 2021-11-19T02:06:30 Z denniskim Biochips (IZhO12_biochips) C++14
100 / 100
 251 ms 411840 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 3 ms 5196 KB Output is correct
4 Correct 15 ms 23116 KB Output is correct
5 Correct 15 ms 25420 KB Output is correct
6 Correct 16 ms 25428 KB Output is correct
7 Correct 219 ms 306976 KB Output is correct
8 Correct 194 ms 307140 KB Output is correct
9 Correct 251 ms 373120 KB Output is correct
10 Correct 250 ms 411840 KB Output is correct