oj.uz

Submission #90094

# Submission time Handle Problem Language Result Execution time Memory
90094 2018-12-20T07:53:22 Z Aydarov03 Biochips (IZhO12_biochips) C++14
0 / 100
 7 ms 4984 KB 
#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;
		cin >> 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

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:53:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("d.in" , "r" , stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
biochips.cpp:54:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("d.out" , "w" , stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4984 KB Output isn't correct
2 Halted 0 ms 0 KB -