#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct node {
ll mx = 0;
int size = 1;
node* l = nullptr;
node* r = nullptr;
node* getl() {
if (l==nullptr) l = new node{};
return l;
}
node* getr() {
if (r == nullptr) r = new node{};
return r;
}
void update(int l, int r, ll x, int tl, int tr) {
if (l <= tl && tr <= r) {
mx = max(mx, x);
return;
}
if (r < tl || tr < l) return;
int mid = (tl+tr) /2;
getl()->update(l, r, x, tl, mid);
getr()->update(l, r, x, mid+1, tr);
size = getl()->size + getr()->size;
}
ll query(int i, int tl, int tr) {
if (tl == tr) return mx;
int mid = (tl+tr) / 2;
ll res = i <= mid ? getl()->query(i, tl, mid) : getr()->query(i, mid+1, tr);
size = (l ? l->size : 0) + (r ? r->size : 0);
return max(mx, res);
}
};
void merge(node*& a, node*& b) {
if (!b) return;
if (!a) a = b;
else {
if (a->size < b->size)
swap(a, b);
a->mx += b->mx;
if (b->l) merge(a->l, b->l);
if (b->r) merge(a->r, b->r);
a->size = (a->l ? a->l->size : 0) + (a->r ? a->r->size : 0);
}
}
int main() {
int n, m, k;
cin >> n >> m >> k;
vector<vector<int>> child(n);
vector par(n, -1);
for (int i = 1; i < n; i++) {
cin >> par[i];
child[--par[i]].push_back(i);
}
map<int,int> comp;
vector<pair<int,int>> fruit(n);
for (int i =0; i < m;i ++) {
ll v, d, w;
cin >> v >> d >> w;
v--;
comp[d] = 0;
fruit[v] = {d, w};
}
k = 0;
for (auto& mp: comp) mp.second = ++k;
for (auto& [d, w] : fruit)
d = comp[d];
function<void(node*)> print = [&](node* st) {
cout << st->mx << '{';
if (st->l) print(st->l);
cout << ',';
if (st->r) print(st->r);
cout << "} ";
};
auto dp = [&](auto& dp, int i)->set<pair<int,int>> {
set<pair<int,int>> res;
int d = fruit[i].first;
#define debug cout << "res=[";for(auto[a,b] : res) cout << a<<':'<<b <<' ';cout << "] ec=[";for (auto [a,b]: ec) cout << a <<':'<<b<<' ';cout << "]\n";
for (int e : child[i]) {
auto ec = dp(dp, e);
if (ec.size() > res.size())
swap(ec, res);
for (auto [j, x] : ec) {
int y = 0;
auto it = res.lower_bound({j+1, -1});
if (it!=res.begin()) {
it--;
y =it->second;
}
it = res.lower_bound({j, -1});
if (it->second == j) {
res.erase(it);
}
res.insert({j, x + y});
}
debug;
}
auto ec = res;
if (d) {
auto it = res.lower_bound({d, -1});
int x = 0;
if (it != res.end()) {
it--;
x = it->second;
}
x += fruit[i].second;
auto jt = res.lower_bound({d, -1});
if (jt != res.end()) {
if (jt->first == d && jt->second < x) {
res.erase(jt);
res.insert({d, x});
}
} else {
res.insert({d, x});
}
cout << d << ' ' << x << '\n';
while (true) {
debug;
auto it = res.lower_bound({d+1, -1});
if (it == res.end() || it->second > x) break;
res.erase(it);
}
}
cout << i << ' '; for (auto [a, b] : res) cout << a<<':'<<b << ' '; cout << endl;
return res;
};
//cout << dp(dp, 0).rbegin()->second << '\n';
if (n <= 10000) {
auto dp2 = [&](auto& dp, int i)->vector<ll>{
vector<vector<ll>> dpc;
for (int e : child[i])
dpc.push_back(dp(dp, e));
vector<ll> res(k+1);
for (int day = 1; day <= k; day++) {
for (int j = 0; j < (int)dpc.size(); j++)
res[day] += dpc[j][day];
}
int d = fruit[i].first;
if (d) {
res[d] = max(res[d], res[d-1] + fruit[i].second);
for (int i = d+1; i <= k; i++)
res[i] = max(res[i], res[d]);
}
return res;
};
cout << dp2(dp2, 0)[k] << '\n';
}
else {
}
}
Compilation message
magictree.cpp: In function 'int main()':
magictree.cpp:88:10: warning: variable 'dp' set but not used [-Wunused-but-set-variable]
88 | auto dp = [&](auto& dp, int i)->set<pair<int,int>> {
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
7360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
106 ms |
7468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
1408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
