Submission #532148

#	Time	Username	Problem	Language	Result	Execution time	Memory
532148		Yazan_Alattar	Magic Tree (CEOI19_magictree)	C++14	100 / 100	133 ms	37272 KiB

magictree

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 100007;
const ll inf = 1e18;
const ll mod = 998244353;
const double pi = acos(-1);
const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
const int block = 320;

vector <int> adj[M];
map <ll,ll> dp[M];
int n, m, k, ripe[M], w[M];

void dfs(int node){
	for(auto i : adj[node]){
		dfs(i);
		if(dp[i].size() > dp[node].size()) swap(dp[i], dp[node]);
		for(auto j : dp[i]) dp[node][j.F] += j.S;
	}
	dp[node][ripe[node]] += w[node];
	
	ll rem = w[node];
	while(1){
		auto i = dp[node].lower_bound(ripe[node] + 1);
		if(i == dp[node].end()) break;
		
		if(i->S > rem){
			i->S -= rem;
			break;
		}
		else{
			rem -= i->S;
			dp[node].erase(i);
		}
	}
	return;
}

int main(){
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 2; i <= n; ++i){
		int p; scanf("%d", &p);
		adj[p].pb(i);
	}
	
	for(int i = 1; i <= m; ++i){
		int x;
		scanf("%d", &x);
		scanf("%d%d", &ripe[x], &w[x]);
	}
	
	dfs(1);
	
	ll ans = 0;
	for(auto i : dp[1]) ans += i.S;
 	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

magictree.cpp: In function 'int main()':
magictree.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d%d%d", &n, &m, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
magictree.cpp:49:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   int p; scanf("%d", &p);
      |          ~~~~~^~~~~~~~~~
magictree.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d", &x);
      |   ~~~~~^~~~~~~~~~
magictree.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   scanf("%d%d", &ripe[x], &w[x]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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