#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
#define pb push_back
#define ff first
#define ss second
typedef long long ll;
const ll INFF = (ll)1e18;
const int INF = (int)1e9;
mt19937 rng(time(NULL));
// increase on interval;
// get key
// basically like dynamic segtree, but with O(n) memory
struct treap{
int y;
int key;
ll val, lazy;
ll maxi;
int cnt = 1;
array<treap*, 2> ch;
treap(int _key, ll _val){
key = _key;
val = _val;
y = rng();
maxi = val;
lazy = 0;
}
};
int getcnt(treap* t){
if(t == NULL) return 0;
else return t->cnt;
}
void recalc(treap *t){
if(t == NULL)
return;
t->cnt = 1;
t->maxi = t->val;
REP(i, 2){
if(t->ch[i] != NULL){
t->maxi = max(t->maxi, t->ch[i]->maxi);
}
t->cnt += getcnt(t->ch[i]);
}
}
void push(treap *t){
if(t == NULL || t->lazy == 0)
return;
REP(i, 2){
if(t->ch[i] != NULL){
t->ch[i]->val += t->lazy;
t->ch[i]->lazy += t->lazy;
t->ch[i]->maxi += t->lazy;
}
}
t->lazy = 0;
}
pair<treap*, treap*> split(treap* t, int k){ // all < k goes left
if(t == NULL)
return {NULL, NULL};
push(t);
if(t->key < k){
auto pa = split(t->ch[1], k);
t->ch[1] = pa.ff;
recalc(t);
return {t, pa.ss};
}
else{
auto pa = split(t->ch[0], k);
t->ch[0] = pa.ss;
recalc(t);
return {pa.ff, t};
}
}
treap* merge(treap* f, treap* s){
if(f == NULL) return s;
if(s == NULL) return f;
if(f->y >= s->y){
push(f);
f->ch[1] = merge(f->ch[1], s);
recalc(f);
return f;
}
else{
push(s);
s->ch[0] = merge(f, s->ch[0]);
recalc(s);
return s;
}
}
treap* add_range(treap *t, int l, int r, ll val){ // all with k >= l && k < r add val
auto pa = split(t, l);
auto pa2 = split(pa.ss, r);
if(pa2.ff != NULL){
pa2.ff->val += val;
pa2.ff->lazy += val;
pa2.ff->maxi += val;
}
pa.ss = merge(pa2.ff, pa2.ss);
treap* res = merge(pa.ff, pa.ss);
return res;
}
treap* get_prev_key(treap *t, int k, ll &val){
auto pa = split(t, k);
if(pa.ff != NULL)
val = pa.ff->maxi;
return merge(pa.ff, pa.ss);
}
treap* get_key(treap* t, int k, ll &val){
auto pa = split(t, k);
auto pa2 = split(pa.ss, k + 1);
if(pa2.ff != NULL)
val = pa2.ff->val;
pa.ss = merge(pa2.ff, pa2.ss);
return merge(pa.ff, pa.ss);
}
treap* insert(treap* t, treap *nv){
if(t == NULL) return nv;
ll val = -1;
t = get_key(t, nv->key, val);
if(val != -1)
return t;
auto pa = split(t, nv->key);
pa.ff = merge(pa.ff, nv);
return merge(pa.ff, pa.ss);
}
void traverse(treap *t, vector<array<ll, 2>> &v){
if(t == NULL)
return;
push(t);
traverse(t->ch[0], v);
v.pb({t->key, t->val});
traverse(t->ch[1], v);
}
void print(treap *t){
vector<array<ll, 2>> els;
traverse(t, els);
REP(i, els.size()){
cout << "[" << els[i][0] << " " << els[i][1] << "], ";
}
cout << "\n";
}
vector<array<ll, 2>> get(treap *t){
vector<array<ll, 2>> els;
traverse(t, els);
return els;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> g(n);
FOR(i, 1, n, 1){
int p;
cin >> p;
p--;
g[p].pb(i);
}
vector<set<array<ll, 2>>> fruits(n);
REP(i, m){
int v, d, w;
cin >> v >> d >> w;
v--;
auto it = fruits[v].lower_bound({d, -INF});
if(it != fruits[v].end() && (*it)[0] == d){
ll nw = (*it)[1] + w;
fruits[v].erase(it);
fruits[v].insert({d, nw});
}
else{
fruits[v].insert({d, w});
}
}
vector<treap*> dp(n, NULL);
function<void(int)> dfs = [&](int v){
for(int x : g[v]){
dfs(x);
}
FOR(i, 1, g[v].size(), 1){
if(getcnt(dp[g[v][i]]) > getcnt(dp[g[v][0]])){
swap(g[v][i], g[v][0]);
swap(dp[g[v][i]], dp[g[v][0]]);
}
}
if(g[v].size() > 0)
swap(dp[v], dp[g[v][0]]); // first merge children, then current fruits
FOR(i, 1, g[v].size(), 1){
vector<array<ll, 2>> tv; // traversal
traverse(dp[g[v][i]], tv);
for(auto x : tv){
ll val = -1;
dp[v] = get_key(dp[v], x[0], val);
if(val == -1){
val = 0;
dp[v] = get_prev_key(dp[v], x[0], val);
dp[v] = insert(dp[v], new treap(x[0], val));
}
}
ll maxi = 0;
REP(j, tv.size()){
if(j != 0){
dp[v] = add_range(dp[v], tv[j - 1][0], tv[j][0], maxi);
}
maxi = max(maxi, tv[j][1]);
}
if(tv.size() > 0) {
dp[v] = add_range(dp[v], tv.back()[0], INF + 5, maxi);
}
}
// merge current fruits
vector<array<ll, 2>> tv; // traversal
for(auto x : fruits[v]){
tv.pb(x);
}
reverse(tv.begin(), tv.end());
for(auto x : tv){
ll val = -1;
dp[v] = get_key(dp[v], x[0], val);
if(val == -1){
val = 0;
dp[v] = get_prev_key(dp[v], x[0], val);
dp[v] = insert(dp[v], new treap(x[0], val));
}
dp[v] = add_range(dp[v], x[0], x[0] + 1, x[1]);
}
//cout << v << " ";
//print(dp[v]);
};
dfs(0);
ll ans = 0;
dp[0] = get_prev_key(dp[0], INF + 10, ans);
cout << ans << "\n";
return 0;
}
Compilation message
magictree.cpp: In function 'void print(treap*)':
magictree.cpp:3:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
| ^
magictree.cpp:5:19: note: in expansion of macro 'FOR'
5 | #define REP(i, n) FOR(i, 0, n, 1)
| ^~~
magictree.cpp:140:5: note: in expansion of macro 'REP'
140 | REP(i, els.size()){
| ^~~
magictree.cpp: In lambda function:
magictree.cpp:3:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
| ^
magictree.cpp:182:9: note: in expansion of macro 'FOR'
182 | FOR(i, 1, g[v].size(), 1){
| ^~~
magictree.cpp:3:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
| ^
magictree.cpp:190:9: note: in expansion of macro 'FOR'
190 | FOR(i, 1, g[v].size(), 1){
| ^~~
magictree.cpp:3:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
| ^
magictree.cpp:5:19: note: in expansion of macro 'FOR'
5 | #define REP(i, n) FOR(i, 0, n, 1)
| ^~~
magictree.cpp:203:13: note: in expansion of macro 'REP'
203 | REP(j, tv.size()){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
312 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
47 ms |
23796 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
588 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
124 ms |
21572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
312 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
4548 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
312 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
312 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
