Submission #1110878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110878		_rain_	Magic Tree (CEOI19_magictree)	C++14	100 / 100	163 ms	41544 KiB

magictree

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

typedef long long LL;
#define name "main"
#define fi first
#define se second
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(b);i>=(a);--i)

const int N=1'00'000;
vector<int>ke[N+2];
void add_edge(int u,int v){
	ke[u].push_back(v),ke[v].push_back(u);
	return;
}
int p[N+2],d[N+2],w[N+2];
int n,m,k;
map<int,LL>mp[N+2];
void dfs(int u,int p){
	mp[u][d[u]]+=w[u];
	for(auto&v:ke[u]){
		if(v==p)continue;
		dfs(v,u);
		if (mp[v].size()>mp[u].size()) swap(mp[u],mp[v]);
		for(auto it:mp[v]){
			mp[u][it.fi]+=it.se;
		}
	}
	if(d[u]==0)return;
	auto it=mp[u].upper_bound(d[u]);
	for(;it!=mp[u].end();){
		if (it->se>w[u]){
			it->se-=w[u];
			return;
		}
		auto tmp=it;
		w[u]-=it->se;++it;mp[u].erase(tmp);
	}
}

int32_t main(){
	scanf("%d%d%d",&n,&m,&k);
	FOR(i,2,n){
		scanf("%d",&p[i]);
		add_edge(i,p[i]);
	}
	FOR(i,1,m){
		int r,ng,gt;scanf("%d%d%d",&r,&ng,&gt);
		d[r]=ng,w[r]=gt;
	}
	dfs(1,0);
	LL ans=0;
	for(auto&it:mp[1]) ans+=it.se;
	printf("%lld",ans);
	exit(0);
}

Compilation message (stderr)

magictree.cpp: In function 'int32_t main()':
magictree.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  scanf("%d%d%d",&n,&m,&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
magictree.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |   scanf("%d",&p[i]);
      |   ~~~~~^~~~~~~~~~~~
magictree.cpp:49:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   int r,ng,gt;scanf("%d%d%d",&r,&ng,&gt);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~

• 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