Submission #211240

#	Time	Username	Problem	Language	Result	Execution time	Memory
211240		Lawliet	Magic Tree (CEOI19_magictree)	C++14	34 / 100	2091 ms	36856 KiB

magictree

#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXK = 30;
const int MAXN = 100010;

int n, m, k;

int t[MAXN];
int w[MAXN];

lli dp[MAXN][MAXK];

vector< int > adj[MAXN];

void DFS(int cur)
{
	for(int i = 0 ; i < adj[cur].size() ; i++)
		DFS( adj[cur][i] );

	for(int j = 1 ; j <= k ; j++)
	{
		lli sum = 0;
		if( t[cur] == j ) sum = w[cur];

		for(int i = 0 ; i < adj[cur].size() ; i++)
			sum += dp[ adj[cur][i] ][j];

		dp[cur][j] = max( dp[cur][j - 1] , sum );
	}
}

int main()
{
	scanf("%d %d %d",&n,&m,&k);

	for(int i = 2 ; i <= n ; i++)
	{
		int p;
		scanf("%d",&p);

		adj[p].push_back( i );
	}

	for(int i = 1 ; i <= m ; i++)
	{
		int node;
		scanf("%d",&node);
		scanf("%d %d",&t[node],&w[node]);
	}

	DFS( 1 );

	printf("%lld\n",dp[1][k]);
}

Compilation message (stderr)

magictree.cpp: In function 'void DFS(int)':
magictree.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
magictree.cpp:28:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < adj[cur].size() ; i++)
                   ~~^~~~~~~~~~~~~~~~~
magictree.cpp: In function 'int main()':
magictree.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&m,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
magictree.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&p);
   ~~~~~^~~~~~~~~
magictree.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&node);
   ~~~~~^~~~~~~~~~~~
magictree.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&t[node],&w[node]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 0 / 3
• Subtask 3: 0 / 11
• Subtask 4: 12 / 12
• Subtask 5: 16 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17