Submission #208169

#	Time	Username	Problem	Language	Result	Execution time	Memory
208169		E869120	Magic Tree (CEOI19_magictree)	C++14	47 / 100	2094 ms	797304 KiB

magictree

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

long long N, P[1 << 18], idx[1 << 18];
long long M, A[1 << 18], B[1 << 18], C[1 << 18];
long long K;
long long dp[100009][1009];
vector<int> X[100009], Y;

int main() {
	scanf("%lld%lld%lld", &N, &M, &K);
	for (int i = 2; i <= N; i++) scanf("%lld", &P[i]);
	for (int i = 1; i <= M; i++) scanf("%lld%lld%lld", &A[i], &B[i], &C[i]);
	for (int i = 2; i <= N; i++) X[P[i]].push_back(i);
	for (int i = 1; i <= M; i++) Y.push_back(B[i]);
	sort(Y.begin(), Y.end());
	Y.erase(unique(Y.begin(), Y.end()), Y.end());
	for (int i = 1; i <= M; i++) B[i] = (lower_bound(Y.begin(), Y.end(), B[i]) - Y.begin()) + 1;
	for (int i = 1; i <= M; i++) idx[A[i]] = i;

	for (int i = N; i >= 1; i--) {
		for (int j : X[i]) {
			for (int k = 0; k <= Y.size(); k++) dp[i][k] += dp[j][k];
		}
		if (idx[i] >= 1) {
			int id = idx[i];
			dp[i][B[id]] += C[id];
		}
		for (int j = 1; j <= Y.size(); j++) dp[i][j] = max(dp[i][j], dp[i][j - 1]);
	}

	cout << dp[1][Y.size()] << endl;
	return 0;
}

Compilation message (stderr)

magictree.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
magictree.cpp: In function 'int main()':
magictree.cpp:26:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k <= Y.size(); k++) dp[i][k] += dp[j][k];
                    ~~^~~~~~~~~~~
magictree.cpp:32:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j <= Y.size(); j++) dp[i][j] = max(dp[i][j], dp[i][j - 1]);
                   ~~^~~~~~~~~~~
magictree.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &N, &M, &K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:15:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 2; i <= N; i++) scanf("%lld", &P[i]);
                               ~~~~~^~~~~~~~~~~~~~~
magictree.cpp:16:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 1; i <= M; i++) scanf("%lld%lld%lld", &A[i], &B[i], &C[i]);
                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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