Submission #90090

#	Time	Username	Problem	Language	Result	Execution time	Memory
90090		Aydarov03	Biochips (IZhO12_biochips)	C++14	0 / 100	6 ms	4984 KiB

biochips

#include <bits/stdc++.h>
using namespace std;

int tik = 1;
int ans;
int a[100005];
int tin[100005];
int tout[100005];
vector <int> g[100005];
vector <int> diff[100005];
int n , m , root;

bool is( int b , int a ) // return b is son of a
{
	return ( tin[a] <= tin[b] && tout[a] >= tout[b] );
}


void dfs( int v , int p = -1 )
{
	tin[v] = tik++;
	
	for(auto to : g[v])
	{
		if( to == p )continue;
		
		dfs( to , v );
	}
	
	tout[v] = tik++;
}


void rec( int v , int sum = 0 , int ost = m - 1)
{
	if( ost == 0 )
	{
		ans = max( ans , sum );
		return;
	}
	
	for(auto to : diff[v])
	{
		rec( to ,  sum + a[to], ost - 1 );
	}
	
}



main()
{
	//freopen("d.in" , "r" , stdin);
	//freopen("d.out" , "w" , stdout);
	
	
	
	cin >> n >> m;
	
	for(int i = 1; i <= n; i++)
	{
		int p , cost;
		scanf("%d%d" , &p , &cost);
		
		a[i] = cost;
		
		if( p == 0 )
		{
			root = i;
			continue;
		}
		
		g[p].push_back( i );
		g[i].push_back( p );
	}
	
	dfs( root );
	
	
	for(int son = 1; son <= n; son++)
	{
		for(int i = son; i <= n; i++)
		{
			if( !is( son , i ) && !is( i , son ) )
			{
				diff[son].push_back( i );
			}
		}
	}
	
	for(int i = 1; i <= n; i++)
	rec( i , a[i] );
	
	cout << ans;
	
}

Compilation message (stderr)

biochips.cpp:51:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
biochips.cpp: In function 'int main()':
biochips.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d" , &p , &cost);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100