Submission #199996

#	Time	Username	Problem	Language	Result	Execution time	Memory
199996		davitmarg	Magic Tree (CEOI19_magictree)	C++17	100 / 100	198 ms	31224 KiB

magictree

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;
 
int n,m,K,d[100005];
LL w[100005],ans;
vector<int> g[100005];
multiset<pair<int,LL>> s[100005];
 
void dfs(int v)
{
	for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i];
		dfs(to);
		if(s[to].size()>s[v].size())
			swap(s[to],s[v]);
		while(!s[to].empty())
		{
			s[v].insert((*s[to].begin()));
			s[to].erase(s[to].begin());
		}
	}
	if(!w[v])
		return;
 
	LL cnt=w[v];
	while(s[v].upper_bound(MP(d[v],mod*mod))!=s[v].end() && cnt)
	{
		auto it=s[v].upper_bound(MP(d[v],mod*mod));
		pair<int,LL> x=(*it);
		s[v].erase(it);
		LL d=min(x.second,cnt);
		cnt-=d;
		x.second-=d;
		if(x.second)
			s[v].insert(x);
	}
 
	s[v].insert(MP(d[v],w[v]));
}
 
int main()
{
	cin>>n>>m>>K;
	for(int i=2;i<=n;i++)
	{
		int p;
		scanf("%d",&p);
		g[p].PB(i);
	}
 
	for(int i=1;i<=m;i++)
	{
		int v;
		scanf("%d",&v);
		scanf("%d%lld",d+v,w+v);
	}
	dfs(1);
	for(auto it=s[1].begin();it!=s[1].end();++it)
		ans+=(*it).second;
	cout<<ans<<endl;
	return 0;
}
 
/*
 
 
 
 
 
 
 
*/

Compilation message (stderr)

magictree.cpp: In function 'void dfs(int)':
magictree.cpp:32:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
magictree.cpp: In function 'int main()':
magictree.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&p);
   ~~~~~^~~~~~~~~
magictree.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&v);
   ~~~~~^~~~~~~~~
magictree.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%lld",d+v,w+v);
   ~~~~~^~~~~~~~~~~~~~~~~~

• 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