#include <bits/stdc++.h>
#define VERBOSE 1
using namespace std;
#define int long long
struct node
{
bool fruit = false;
int day,where,weight;
vector<int> children;
set<pair<int,int> > harvest;
};
vector<node> tree;
int depth(int v)
{
int ans = 0;
for(int c : tree[v].children)
ans = max(ans,depth(c)+1);
return ans;
}
// merge solutions in tree[from] and tree[in]
// merge from smaller set into larger
// return index of smaller set
int join_sol(int in,int from)
{
if(tree[from].harvest.size() > tree[in].harvest.size())
swap(in,from);
for(auto it = tree[from].harvest.begin(); it!=tree[from].harvest.end();it++)
{
int day = it->first, add = it->second;
auto inptr = tree[in].harvest.lower_bound({day,-1});
if(inptr == tree[in].harvest.end() || inptr->first != day)
{
tree[in].harvest.insert({day,add});
}
else //(inptr->first == day)
{
pair<int,int> tmp = {inptr->first, inptr->second};
tmp.second += add;
tree[in].harvest.erase(inptr);
tree[in].harvest.insert(tmp);
}
}
return in;
}
void solve(int v)
{
tree[v].where = v;
tree[v].harvest.insert({-1,0});
for(int c : tree[v].children)
{
solve(c);
tree[v].where = join_sol(tree[v].where,tree[c].where);
}
int w = tree[v].where;
if(tree[v].fruit)
{
auto it = tree[w].harvest.lower_bound({tree[v].day,-1});
if(it == tree[w].harvest.end())
tree[w].harvest.insert({ tree[v].day, tree[v].weight });
else if( it->first == tree[v].day)
{
pair<int,int> newval = {it->first,it->second+tree[v].weight};
tree[w].harvest.erase(it);
it = tree[w].harvest.insert(newval).first;
int debt = tree[v].weight;
while(debt)
{
auto rn = it;
rn++;
if(rn == tree[w].harvest.end()) break;
pair<int,int> tmp = {rn->first,rn->second};
tree[w].harvest.erase(rn);
int take = min(debt, tmp.second);
debt -= take;
tmp.second -= take;
if(tmp.second)
tree[w].harvest.insert(tmp);
}
}
else
{
it = tree[w].harvest.insert({tree[v].day, tree[v].weight}).first;
int debt = tree[v].weight;
while(debt)
{
auto rn = it;
rn++;
if(rn == tree[w].harvest.end()) break;
pair<int,int> tmp = {rn->first,rn->second};
tree[w].harvest.erase(rn);
int take = min(debt, tmp.second);
debt -= take;
tmp.second -= take;
if(tmp.second)
tree[w].harvest.insert(tmp);
}
}
}
}
main()
{
int n,m,k;
cin >> n >> m >> k;
tree.resize(n);
for(int i=1;i<n;++i)
{
int parent;
cin >> parent;
parent--;
tree[parent].children.push_back(i);
}
for(int i=0;i<m;++i)
{
int pos;
cin >> pos;
pos--;
tree[pos].fruit = true;
cin >> tree[pos].day >> tree[pos].weight;
}
solve(0);
int ans = 0;
for(auto it = tree[ tree[0].where ].harvest.begin(); it != tree[ tree[0].where ].harvest.end(); it++)
ans += it->second;
cout << ans << "\n";
if(VERBOSE)
{
cerr << "depth " << depth(0) << "\n";
}
}
Compilation message
magictree.cpp:115:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
235 ms |
26340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
310 ms |
22408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
4144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
