#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define MAX 101010
#define MAXS 20
#define ln '\n'
struct segtree {
ll N, s;
vector<ll> tree, l, r;
void init(ll x = 1) {
if (x >= s) {
l[x] = r[x] = x - s + 1;
return;
}
init(x * 2);
init(x * 2 + 1);
l[x] = l[x * 2];
r[x] = r[x * 2 + 1];
}
segtree(ll n) {
N = n;
s = 1LL << (ll)ceil(log2(N));
tree.resize(2 * s + 1);
l.resize(2 * s + 1);
r.resize(2 * s + 1);
init();
}
void update(ll x, ll a) {
x += s - 1;
tree[x] = max(tree[x], a);
x /= 2;
while (x) {
tree[x] = max(tree[x * 2], tree[x * 2 + 1]);
x /= 2;
}
}
ll query(ll low, ll high, ll loc = 1) {
if (low > high) return 0;
if (l[loc] == low && r[loc] == high) return tree[loc];
if (r[loc * 2] >= high) return query(low, high, loc * 2);
if (l[loc * 2 + 1] <= low) return query(low, high, loc * 2 + 1);
return max(query(low, r[loc * 2], loc * 2), query(l[loc * 2 + 1], high, loc * 2 + 1));
}
segtree() {}
};
struct Fruit {
ll v;
ll w;
};
ll sp[MAX][MAXS];
ll cnt = 0;
ll ord[MAX];
ll dp[MAX];
pll range[MAX];
vector<ll> adj[MAX];
vector<Fruit> fruit[MAX];
ll depth[MAX];
bool cmp(Fruit i, Fruit j) {
return depth[i.v] < depth[j.v];
}
ll dfs(ll x = 1, ll p = 0, ll d = 0) {
ord[x] = ++cnt;
depth[x] = d;
ll mx = ord[x];
for (auto v : adj[x]) {
if (v == p) continue;
mx = max(mx, dfs(v, x, d + 1));
}
range[x] = { ord[x], mx };
return mx;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
ll N, M, K;
cin >> N >> M >> K;
ll i, j;
for (i = 2; i <= N; i++) {
cin >> sp[i][0];
adj[sp[i][0]].push_back(i);
adj[i].push_back(sp[i][0]);
}
for (i = 1; i <= N; i++) {
for (j = 1; j < MAXS; j++) sp[i][j] = sp[sp[i][j - 1]][j - 1];
}
ll a;
Fruit f;
for (i = 1; i <= M; i++) {
cin >> f.v >> a >> f.w;
fruit[a].push_back(f);
}
dfs();
/*
segtree rmq;
rmq = segtree(N);
for (i = 1; i <= K; i++) {
for (auto f : fruit[i]) {
ll v = f.v;
ll w = f.w;
ll sum = 0;
for (auto x : adj[v]) {
if (x == sp[v][0]) continue;
sum += rmq.query(range[x].first, range[x].second);
}
rmq.update(ord[v], sum + w);
}
}
cout << rmq.query(2, N) << ln;
*/
for (i = K; i >= 1; i--) {
sort(fruit[i].begin(), fruit[i].end(), cmp);
for (auto f : fruit[i]) {
ll v = f.v;
ll w = f.w;
ll d = w - dp[v];
d = max(d, 0LL);
while (v) {
dp[v] += d;
v = sp[v][0];
}
}
}
cout << dp[1] << ln;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5072 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
29304 KB |
Output is correct |
| 2 |
Execution timed out |
2069 ms |
31832 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
132 ms |
30136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5072 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
9816 KB |
Output is correct |
| 2 |
Correct |
77 ms |
28532 KB |
Output is correct |
| 3 |
Correct |
72 ms |
28516 KB |
Output is correct |
| 4 |
Correct |
62 ms |
28464 KB |
Output is correct |
| 5 |
Correct |
32 ms |
28600 KB |
Output is correct |
| 6 |
Incorrect |
203 ms |
30148 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5072 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5068 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
5072 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
