#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define X first
#define Y second
#define MP make_pair
using namespace std;
const int N = 1e5 + 1;
const ll INF = 1e7;
typedef map<int, ll> DP;
int n, m, k;
vector< int > g[N];
DP dp[N];
pair<int, int> bomb[N];
ostream& operator<< (ostream& out, DP& a) {
for(auto [pos, val]: a) {
out << pos << " " << val << "\n";
}
return out;
}
void insert(ll cost, int pos, DP &v) {
v[pos] += cost;
DP::iterator it = v.upper_bound(pos);
ll add = 0;
while(it != v.end()) {
if(it->second + add - cost <= 0) {
add += it->second;
v.erase(it++);
}
else {
it->second += add - cost;
break;
}
}
}
void merge(DP &child, DP &v) {
while(!child.empty()) {
ll cost = child.begin()->second;
int pos = child.begin()->first;
child.erase(child.begin());
v[pos] += cost;
DP::iterator it = v.upper_bound(pos);
if(it != v.end())
it->second -= cost;
}
/*
ll cost = 0;
int pos = 0;
while(!child.empty()) {
cost += child.begin()->second;
pos = child.begin()->first;
child.erase(child.begin());
insert(cost, pos, v);
}*/
}
void dfs(int v) {
//cerr << v << "\n";
for(int to: g[v]) {
dfs(to);
if(dp[v].size() > dp[to].size())
dp[v].swap(dp[to]);
merge(dp[to], dp[v]);
}
insert(bomb[v].Y, bomb[v].X, dp[v]);
//cerr << "\n" << dp[v] << "\n";
//cerr << v << "\n";
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> k;
for(int i = 2, v;i <= n;i++) {
cin >> v;
g[v].push_back(i);
}
for(int i = 0;i < m;i++) {
int v, d, w;
cin >> v >> d >> w;
bomb[v] = {d, w};
}
dfs(1);
ll res = 0;
for(auto [pos, val]: dp[1]) {
res += val;
}
cout << res;
}
Compilation message
magictree.cpp: In function 'std::ostream& operator<<(std::ostream&, DP&)':
magictree.cpp:24:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
24 | for(auto [pos, val]: a) {
| ^
magictree.cpp: In function 'int main()':
magictree.cpp:104:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
104 | for(auto [pos, val]: dp[1]) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
389 ms |
11968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7380 KB |
Output is correct |
| 3 |
Correct |
23 ms |
7512 KB |
Output is correct |
| 4 |
Correct |
79 ms |
20888 KB |
Output is correct |
| 5 |
Execution timed out |
2085 ms |
21392 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
11856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
7892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
