#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
using namespace std;
#define int long long
struct node{
int s;
int left;
int right;
int cnt;
bool clear;
node(){
s = 0;
left = -1;
right = -1;
cnt = 0;
clear = false;
}
};
node free_node;
int k;
struct Dynamic_Segment_Tree{
vector<node> t;
void clear(int v, int l, int r, int L, int R){
if(v == -1) return;
if(l == L && r == R){
t[v].clear = true;
t[v].cnt = 0;
t[v].s = 0;
return;
}
int m = (l + r) >> 1;
if(m < L) clear(t[v].right, m+1, r, L, R);
else if(m >= R) clear(t[v].left, l, m, L, R);
else{
clear(t[v].right, m+1, r, m+1, R);
clear(t[v].left, l, m, L, m);
}
t[v].s = sum(t[v].left) + sum(t[v].right);
t[v].cnt = (t[v].left != -1 ? t[t[v].left].cnt : 0) +
(t[v].right != -1 ? t[t[v].right].cnt : 0);
}
void clear(int l, int r){
if(l > r) return;
clear(0, 1, k, l, r);
}
int get_sum(int v, int l, int r, int L, int R){
// cout << v << ' ' << l << ' ' << r << ' ' << L << ' ' << R << ' ' << t.size() << endl;
if(v == -1 || t[v].clear) return 0;
if(l == L && r == R) return t[v].s;
int m = (l + r) >> 1;
// cout << v << ' ' << l << ' ' << r << ' ' << L << ' ' << R << endl;
if(L > m) return get_sum(t[v].right, m+1, r, L, R);
if(m >= R) return get_sum(t[v].left, l, m, L, R);
return get_sum(t[v].left, l, m, L, m) + get_sum(t[v].right, m+1, r, m+1, R);
}
int get_sum(int l, int r){
return l > r ? 0 : get_sum(0, 1, k, l, r);
}
Dynamic_Segment_Tree(){
t.clear();
t.push_back(free_node);
}
int left_side(int v){
if(t[v].left == -1){
t[v].left = t.size();
t.push_back(free_node);
}
return t[v].left;
}
int sum(int v){
return v == -1 ? 0 : t[v].s;
}
int right_side(int v){
if(t[v].right == -1){
t[v].right = t.size();
t.push_back(free_node);
}
return t[v].right;
}
void add(int v, int l, int r, int id, int w){
if(l == r){
t[v].s += w;
t[v].cnt = 1;
t[v].clear = false;
return;
}
int m = (l + r) >> 1;
if(t[v].clear){
clear(t[v].left, l, m, l, m);
clear(t[v].right, m+1, r, m+1, r);
t[v].clear = false;
}
if(id <= m) add(left_side(v), l, m, id, w);
else add(right_side(v), m+1, r, id, w);
t[v].s = sum(t[v].left) + sum(t[v].right);
t[v].cnt = (t[v].left != -1 ? t[t[v].left].cnt : 0) +
(t[v].right != -1 ? t[t[v].right].cnt : 0);
}
void add(int id, int w){
add(0, 1, k, id, w);
}
void merge(int v, int l, int r, Dynamic_Segment_Tree&d, int vd){
if(l == r){
if(t[v].s == 0)
t[v].cnt = 1;
t[v].s += d.t[vd].s;
return;
}
int m = (l + r) >> 1;
if(t[v].clear){
clear(t[v].left, l, m, l, m);
clear(t[v].right, m+1, r, m+1, r);
t[v].clear = false;
}
if(d.t[vd].left != -1 && d.t[d.t[vd].left].cnt > 0)
merge(left_side(v), l, m, d, d.t[vd].left);
if(d.t[vd].right != -1 && d.t[d.t[vd].right].cnt > 0)
merge(right_side(v), m+1, r, d, d.t[vd].right);
t[v].s = sum(t[v].left) + sum(t[v].right);
t[v].cnt = (t[v].left != -1 ? t[t[v].left].cnt : 0) +
(t[v].right != -1 ? t[t[v].right].cnt : 0);
}
void merge(Dynamic_Segment_Tree& d){
merge(0, 1, k, d, 0);
d.t.clear();
d.t.shrink_to_fit();
}
};
Dynamic_Segment_Tree free_seg_tree;
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
// cout << free_seg_tree.t.size() << endl;
int n, m;
cin >> n >> m >> k;
vector<int> seg_id(n, -1);
vector<Dynamic_Segment_Tree> seg_tree;
vector<vector<int> > g(n);
vector<pair<int, int> > q(n, make_pair(-1, -1));
for(int i = 2, f; i <= n; i ++){
cin >> f;
g[f-1].push_back(i-1);
}
for(int i = 0, v, d, w; i < m; i ++){
cin >> v >> d >> w;
q[v-1] = make_pair(d, w);
}
for(int u = n-1; u >= 0; u --){
// cout << u << endl;
if(g[u].empty()){
if(q[u].first == -1) continue;
seg_id[u] = seg_tree.size();
seg_tree.push_back(free_seg_tree);
seg_tree[seg_id[u]].add(q[u].first, q[u].second);
}
else{
sort(g[u].begin(), g[u].end(), [&](int r, int l){
if(seg_id[r] == -1) return false;
if(seg_id[l] == -1) return true;
return seg_tree[seg_id[r]].t[0].cnt > seg_tree[seg_id[l]].t[0].cnt;
});
// cout << u << "-" << endl;
if(seg_id[g[u][0]] == -1) continue;
seg_id[u] = seg_id[g[u][0]];
for(int i = 1; i < g[u].size() && seg_id[g[u][i]] != -1; i ++)
seg_tree[seg_id[u]].merge(seg_tree[seg_id[g[u][i]]]);
// cout << u << "--" << endl;
if(q[u].first == -1) continue;
if(seg_tree[seg_id[u]].get_sum(q[u].first+1, k) < q[u].second){
// cout << u << "---" << endl;
seg_tree[seg_id[u]].clear(q[u].first+1, k);
seg_tree[seg_id[u]].add(q[u].first, q[u].second);
}
}
}
cout << seg_tree[seg_id[0]].t[0].s;
return 0;
}
Compilation message
magictree.cpp: In function 'int main()':
magictree.cpp:175:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
175 | for(int i = 1; i < g[u].size() && seg_id[g[u][i]] != -1; i ++)
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
51052 KB |
Output is correct |
| 2 |
Correct |
61 ms |
38968 KB |
Output is correct |
| 3 |
Correct |
288 ms |
142784 KB |
Output is correct |
| 4 |
Correct |
177 ms |
122780 KB |
Output is correct |
| 5 |
Correct |
208 ms |
135460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
11940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
