#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 = 1e6 + 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;
for (auto i = a.lwb(k.fi+1);i != a.end(); i = a.lwb(i->fi+1)) {
if (i->se > last) {
i->se -= last;
break;
} else {
last -= i->se;
a.erase(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:47:23: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
47 | mll& mg(mll &a, mll &b) {
| ^
magictree.cpp:47:23: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
magictree.cpp:53:16: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
53 | void DFS(ll now) {
| ^
magictree.cpp:53:16: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
magictree.cpp:77:11: warning: bad option '-f no-stack-protector' to attribute 'optimize' [-Wattributes]
77 | int main () {
| ^
magictree.cpp:77:11: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
70732 KB |
Output is correct |
2 |
Correct |
36 ms |
70688 KB |
Output is correct |
3 |
Correct |
32 ms |
70708 KB |
Output is correct |
4 |
Correct |
34 ms |
70732 KB |
Output is correct |
5 |
Correct |
32 ms |
70724 KB |
Output is correct |
6 |
Correct |
33 ms |
70776 KB |
Output is correct |
7 |
Correct |
34 ms |
70732 KB |
Output is correct |
8 |
Correct |
33 ms |
70764 KB |
Output is correct |
9 |
Correct |
35 ms |
70776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
264 ms |
222024 KB |
Output is correct |
2 |
Runtime error |
812 ms |
1048580 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
71080 KB |
Output is correct |
2 |
Correct |
38 ms |
72436 KB |
Output is correct |
3 |
Correct |
45 ms |
83268 KB |
Output is correct |
4 |
Correct |
112 ms |
122392 KB |
Output is correct |
5 |
Runtime error |
736 ms |
1048580 KB |
Execution killed with signal 9 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
113 ms |
84108 KB |
Output is correct |
2 |
Correct |
105 ms |
82304 KB |
Output is correct |
3 |
Correct |
95 ms |
93868 KB |
Output is correct |
4 |
Correct |
81 ms |
87408 KB |
Output is correct |
5 |
Correct |
90 ms |
100968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
70732 KB |
Output is correct |
2 |
Correct |
36 ms |
70688 KB |
Output is correct |
3 |
Correct |
32 ms |
70708 KB |
Output is correct |
4 |
Correct |
34 ms |
70732 KB |
Output is correct |
5 |
Correct |
32 ms |
70724 KB |
Output is correct |
6 |
Correct |
33 ms |
70776 KB |
Output is correct |
7 |
Correct |
34 ms |
70732 KB |
Output is correct |
8 |
Correct |
33 ms |
70764 KB |
Output is correct |
9 |
Correct |
35 ms |
70776 KB |
Output is correct |
10 |
Correct |
159 ms |
107204 KB |
Output is correct |
11 |
Correct |
140 ms |
98504 KB |
Output is correct |
12 |
Correct |
217 ms |
202836 KB |
Output is correct |
13 |
Correct |
212 ms |
199364 KB |
Output is correct |
14 |
Correct |
190 ms |
205708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
73672 KB |
Output is correct |
2 |
Correct |
70 ms |
78512 KB |
Output is correct |
3 |
Correct |
77 ms |
78152 KB |
Output is correct |
4 |
Correct |
68 ms |
79676 KB |
Output is correct |
5 |
Runtime error |
773 ms |
1048580 KB |
Execution killed with signal 9 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
70732 KB |
Output is correct |
2 |
Correct |
36 ms |
70688 KB |
Output is correct |
3 |
Correct |
32 ms |
70708 KB |
Output is correct |
4 |
Correct |
34 ms |
70732 KB |
Output is correct |
5 |
Correct |
32 ms |
70724 KB |
Output is correct |
6 |
Correct |
33 ms |
70776 KB |
Output is correct |
7 |
Correct |
34 ms |
70732 KB |
Output is correct |
8 |
Correct |
33 ms |
70764 KB |
Output is correct |
9 |
Correct |
35 ms |
70776 KB |
Output is correct |
10 |
Correct |
35 ms |
71080 KB |
Output is correct |
11 |
Correct |
38 ms |
72436 KB |
Output is correct |
12 |
Correct |
45 ms |
83268 KB |
Output is correct |
13 |
Correct |
112 ms |
122392 KB |
Output is correct |
14 |
Runtime error |
736 ms |
1048580 KB |
Execution killed with signal 9 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
70732 KB |
Output is correct |
2 |
Correct |
36 ms |
70688 KB |
Output is correct |
3 |
Correct |
32 ms |
70708 KB |
Output is correct |
4 |
Correct |
34 ms |
70732 KB |
Output is correct |
5 |
Correct |
32 ms |
70724 KB |
Output is correct |
6 |
Correct |
33 ms |
70776 KB |
Output is correct |
7 |
Correct |
34 ms |
70732 KB |
Output is correct |
8 |
Correct |
33 ms |
70764 KB |
Output is correct |
9 |
Correct |
35 ms |
70776 KB |
Output is correct |
10 |
Correct |
264 ms |
222024 KB |
Output is correct |
11 |
Runtime error |
812 ms |
1048580 KB |
Execution killed with signal 9 |
12 |
Halted |
0 ms |
0 KB |
- |