#include <iostream>
#include <set>
#include <vector>
int n,m,k;
using namespace std;
typedef long long ll;
typedef set<pair<int,ll>> sp;
typedef pair<int,int> pi;
void add(sp &a, int from, ll v) {
auto q = a.lower_bound({from,0});
bool b = false;
while(true) {
auto q = a.lower_bound({from,0});
if(q==a.end()) break;
if(q->second<v) {
bool b = true;
a.erase(q);
}else break;
}
a.insert({from,v});
}
ll eval(sp &a, int at) {
auto q = a.lower_bound({at+1,0});
--q;
return q->second;
}
sp un(sp &a, sp &b) {
sp res;
auto q = a.begin();
auto p = b.begin();
int pos = 0;
ll vala = 0;
ll valb = 0;
while(!((q==a.end()) &&(p==b.end()))) {
res.insert({pos,vala+valb});
if(q==a.end()) {
++p;
valb= p->second;
pos = p->first;
}else if(p==b.end()) {
++q;
vala= q->second;
pos = q->first;
}else {
if(q->second>p->second) {
++p;
valb= p->second;
pos = p->first;
}else {
++q;
vala= q->second;
pos = q->first;
}
}
}
return res;
}
sp dfs(int cur, vector<vector<int>> &c,vector<pair<int,int>> &f) {
if(c[cur].empty()) {
sp a = {{0,0}};
add(a,f[cur].first,f[cur].second);
return a;
}else {
vector<sp> sets;
int locmax = 0;
int valmax = 0;
for (int i :c[cur]) {
sets.push_back(dfs(i,c,f));
if(sets.back().size()>valmax) {
locmax= sets.size()-1;
valmax = sets.back().size();
}
}
for (int i = 0; i < sets.size(); ++i) {
if(i==locmax) continue;
sets[locmax] = un(sets[locmax],sets[i]);
}
if(f[cur].second!= 0) {
ll a = eval(sets[locmax], f[cur].first);
add(sets[locmax],f[cur].first,f[cur].second+a);
}
return sets[locmax];
}
}
int main()
{
cin>>n>>m>>k;
vector<vector<int>> c(n);
for (int i = 1; i < n; ++i) {
int x; cin>>x; x--;
c[x].push_back(i);
}
vector<pair<int,int>> f(n,{0,0});
for (int i = 0; i < m; ++i) {
int x,y,z; cin>>x>>y>>z; x--; y--;
f[x]={y,z};
}
sp s = dfs(0,c,f);
cout<<eval(s,k)<<endl;
}
Compilation message
magictree.cpp: In function 'void add(sp&, int, ll)':
magictree.cpp:16:18: warning: unused variable 'b' [-Wunused-variable]
16 | bool b = true;
| ^
magictree.cpp:10:10: warning: variable 'q' set but not used [-Wunused-but-set-variable]
10 | auto q = a.lower_bound({from,0});
| ^
magictree.cpp:11:10: warning: unused variable 'b' [-Wunused-variable]
11 | bool b = false;
| ^
magictree.cpp: In function 'sp dfs(int, std::vector<std::vector<int> >&, std::vector<std::pair<int, int> >&)':
magictree.cpp:69:34: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
69 | if(sets.back().size()>valmax) {
| ~~~~~~~~~~~~~~~~~~^~~~~~~
magictree.cpp:74:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::set<std::pair<int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for (int i = 0; i < sets.size(); ++i) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
535 ms |
13604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
592 KB |
Output is correct |
| 2 |
Correct |
2 ms |
592 KB |
Output is correct |
| 3 |
Correct |
5 ms |
592 KB |
Output is correct |
| 4 |
Correct |
138 ms |
26908 KB |
Output is correct |
| 5 |
Execution timed out |
2075 ms |
28052 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
126 ms |
5192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
1872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
