Submission #208150

#	Time	Username	Problem	Language	Result	Execution time	Memory
208150		junodeveloper	Magic Tree (CEOI19_magictree)	C++17	100 / 100	157 ms	40568 KiB

magictree

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define fi first
#define se second
#define mset(x,y) memset(x,y,sizeof(x))
#define rep(i,a,b) for(int i(a);i<=(b);i++)
#define repr(i,a,b) for(int i(a);i>=(b);i--)
using namespace std;
#ifdef LOCAL
#define dmp(...) _dmp(#__VA_ARGS__, __VA_ARGS__)
#else
#define dmp(...) (__VA_ARGS__)
#endif
template<class TH> void _dmp(const char *sdbg, TH h){cout<<sdbg<<"="<<h<<endl;}
template<class TH, class... TA> void _dmp(const char *sdbg, TH h, TA...a){
while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
}
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
int n,m,D;
vi adj[100010];
pll a[100010];
multimap<ll,ll>* st[100010];
void solve(int u) {
	for(auto& it:adj[u])solve(it);
	if(adj[u].empty()) {
		st[u]=new multimap<ll,ll>();
	} else {
		int mx=0;
		for(auto& it:adj[u])mx=max(mx,(int)st[it]->size());
		for(auto& it:adj[u])
			if(st[it]->size()==mx) {
				st[u]=st[it];
				break;
			}
		for(auto& it:adj[u]) {
			if(st[it]==st[u])continue;
			for(auto& jt:*st[it])st[u]->insert(jt);
		}
	}
	if(a[u].fi!=-1) {
		auto it=st[u]->lower_bound(a[u].fi+1);
		ll sum=0;
		while(it!=st[u]->end()) {
			ll tmp=it->se;
			it->se+=sum; sum+=tmp;
			if(it->se>a[u].se){ 
				it->se-=a[u].se;
				break;
			}
			it=st[u]->erase(it);
		}
		st[u]->insert({a[u].fi,a[u].se});
	}
}
void MAIN() {
	cin>>n>>m>>D;
	rep(i,1,n) {
		adj[i].clear();
		a[i]={-1,-1};
	}
	rep(i,2,n) {
		int p;
		cin>>p;
		adj[p].pb(i);
	}
	rep(i,1,m) {
		int v,d,w;
		cin>>v>>d>>w;
		a[v]={d,w};
	}
	solve(1);
	ll ans=0;
	for(auto& it:*st[1])ans+=it.se;
	cout<<ans;
}
int main() {
	ios::sync_with_stdio(false);cin.tie(0);
	int T=1;
	for(int tt=1;tt<=T;tt++) {
		MAIN();
	}
	return 0;
}

Compilation message (stderr)

magictree.cpp: In function 'void _dmp(const char*, TH, TA ...)':
magictree.cpp:20:1: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
 while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
 ^~~~~
magictree.cpp:20:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
 while(*sdbg!=',')cout<<*sdbg++;cout<<"="<<h<<","; _dmp(sdbg+1, a...);
                                ^~~~
magictree.cpp: In function 'void solve(int)':
magictree.cpp:41:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(st[it]->size()==mx) {
       ~~~~~~~~~~~~~~^~~~

• 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