oj.uz

Submission #488451

# Submission time Handle Problem Language Result Execution time Memory
488451 2021-11-19T01:43:04 Z denniskim Biochips (IZhO12_biochips) C++14
0 / 100
 258 ms 524292 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][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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 5008 KB Output is correct
3 Correct 3 ms 5388 KB Output is correct
4 Correct 22 ms 40208 KB Output is correct
5 Correct 25 ms 44644 KB Output is correct
6 Correct 23 ms 44680 KB Output is correct
7 Runtime error 258 ms 524292 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -