#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ll=long long;
using ii=pair<int,int>;
using pll=pair<ll,ll>;
const int mxN = 1e5+5;
const int mxM = mxN;
const int mxK = 1e5+5;
int N, M, K;
vector<int> al[mxN];
ii fruit[mxN];
set<ii> dfs(int u) {
set<ii> cur;
for (int v : al[u]) {
auto x = dfs(v);
if (SZ(cur) < SZ(x)) swap(cur,x);
for (auto y : x) cur.insert(y);
}
if (fruit[u] != ii(-1,-1)) {
ll sum = 0;
auto x = cur.lower_bound(ii(fruit[u].first+1,0));
if (!cur.empty()) for (auto it = prev(cur.end());; --it) {
sum += it->second;
if (it == x) break;
}
if (fruit[u].second >= sum) {
if (!cur.empty()) for (auto it = prev(cur.end());;) {
auto jt = (it == x ? cur.end() : prev(it));
cur.erase(it);
if (it == x) break;
it = jt;
}
cur.insert(fruit[u]);
}
}
return cur;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M >> K;
FOR(i,2,N){
int P; cin >> P;
al[P].push_back(i);
}
FOR(i,1,N) fruit[i] = ii(-1,-1);
FOR(i,1,M){
int V, D, W; cin >> V >> D >> W;
fruit[V] = ii(D,W);
}
auto ans = dfs(1);
ll sum = 0;
for (auto& x : ans) {
sum += x.second;
}
cout << sum << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2087 ms |
2688 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
6520 KB |
Output is correct |
2 |
Correct |
52 ms |
13560 KB |
Output is correct |
3 |
Correct |
135 ms |
8840 KB |
Output is correct |
4 |
Correct |
89 ms |
8176 KB |
Output is correct |
5 |
Correct |
103 ms |
9976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2083 ms |
2816 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2098 ms |
5112 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2087 ms |
2688 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2085 ms |
3200 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2087 ms |
2688 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2087 ms |
2688 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |