#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops, no-stack-protector, Ofast")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll INF = (1LL<<60);
const ll N = 1e3 + 5;
const ll MOD = 1e9 + 7;
const ld pi = acos(-1);
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()
#define setp setprecision
typedef map<ll, ll> mll;
// FOR DEBUG PURPOSE
ostream& operator << (ostream& out, mll k) {
for (auto i : k) {
out << "{" << i.fi << ", " << i.se << "} ";
}
return out;
}
ll d[N], w[N], n, m, t;
vector<ll> v[N];
mll dp[N];
void insert(mll &a, pll k) {
ll last = k.se;
vector<ll> era;
for (auto i = a.lwb(k.fi+1);i != a.end(); i = a.lwb(i->fi+1)) {
if (i->se > last) {
i->se -= last;
} else {
last -= i->se;
era.pb(i->fi);
}
}
for (ll i : era) {
a.erase(a.find(i));
}
a[k.fi] += k.se;
}
mll& mg(mll &a, mll &b) {
if (SZ(a) > SZ(b)) swap(a, b);
for (auto i : a) b[i.fi] += i.se;
return b;
}
void DFS(ll now) {
for (ll to : v[now]) {
DFS(to);
dp[now] = mg(dp[now], dp[to]);
}
if (w[now]) {
insert(dp[now], {d[now], w[now]});
}
//cout << "NODE::" << now << " " << dp[now] << "\n";
/*
for (ll j = 0;j <= t; ++j) {
dp[now][j] = (j == d[now] ? w[now] : 0);
for (ll to : v[now]) {
ll ma = 0;
for (ll k = 0;k <= j; ++k) {
ma = max(ma, dp[to][k]);
}
dp[now][j] += ma;
}
}
*/
}
int main () {
ios_base::sync_with_stdio(0);
cin >> n >> m >> t;
for (ll i = 2, x;i <= n; ++i) {
cin >> x;
v[x].pb(i);
}
for (ll i = 0, x;i < m; ++i) {
cin >> x;
cin >> d[x] >> w[x];
}
DFS(1);
ll ans = 0;
for (auto i : dp[1]) {
ans += i.se;
}
cout << ans << "\n";
return 0;
}
Compilation message
magictree.cpp:2:63: warning: bad option '-f no-stack-protector' to pragma 'optimize' [-Wpragmas]
2 | #pragma GCC optimize("unroll-loops, no-stack-protector, Ofast")
| ^
magictree.cpp:2:63: warning: bad option '-f Ofast' to pragma 'optimize' [-Wpragmas]
magictree.cpp:22:42: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
22 | ostream& operator << (ostream& out, mll k) {
| ^
magictree.cpp:22:42: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
magictree.cpp:33:26: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
33 | void insert(mll &a, pll k) {
| ^
magictree.cpp:33:26: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
magictree.cpp:50:23: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
50 | mll& mg(mll &a, mll &b) {
| ^
magictree.cpp:50:23: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
magictree.cpp:56:16: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
56 | void DFS(ll now) {
| ^
magictree.cpp:56:16: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
magictree.cpp:80:11: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
80 | int main () {
| ^
magictree.cpp:80:11: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
588 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 |
3 ms |
1936 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
716 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
0 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
