#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using pii = pair<int,int>;
using ll = long long;
const int nmax = 1e5 + 5, inf = 1e9 + 5;
int n, m, k;
vector<int> g[nmax];
#define lsb(x) (x & -x)
namespace AIB {
vector<ll> rez(1); int len = 0;
void append(int n) {
len += n;
rez.resize(rez.size() + n);
}
void upd(int x, int val) {
while(x <= len)
rez[x] += val,
x += lsb(x);
}
int query(int x) {
ll sum = 0;
while(x > 0)
sum += rez[x],
x -= lsb(x);
return min((ll)inf, sum);
}
int query(int l, int r) { return query(r) - query(l - 1); }
}
pii vec[nmax]; // zi, cost
int preord[nmax], pin[nmax], pout[nmax], inp = 1;
namespace AINT {
vector<pii> list[nmax * 4];
int left[nmax], right[nmax];
void initAIB(int node = 1, int cl = 1, int cr = n) {
left[node] = AIB::rez.size();
AIB::append(cr - cl + 1);
right[node] = AIB::rez.size() - 1;
if(cl == cr)
return;
int mid = cl + cr >> 1;
initAIB(2 * node, cl, mid);
initAIB(2 * node + 1, mid + 1, cr);
}
void initAINT(int node = 1, int cl = 1, int cr = n) {
if(cl == cr) {
list[node].push_back(vec[preord[cl]]);
AIB::upd(left[node], list[node].back().second);
return;
}
int mid = cl + cr >> 1;
initAINT(2 * node, cl, mid);
initAINT(2 * node + 1, mid + 1, cr);
int p[2] = {0, 0}, l = 2 * node, r = 2 * node + 1;
while(p[0] < list[l].size()) {
if(list[l][p[0]] > list[r][p[1]])
swap(l, r),
swap(p[0], p[1]);
list[node].push_back(list[l][p[0]]);
p[0]++;
}
while(p[1] < list[r].size())
list[node].push_back(list[r][p[1]++]);
for(int i = 0; i < list[node].size(); i++)
AIB::upd(left[node] + i, list[node][i].second);
return;
}
int query(int l, int r, int val, int node = 1, int cl = 1, int cr = n) {
if(r < cl || cr < l)
return 0;
if(l <= cl && cr <= r)
return AIB::query(upper_bound(all(list[node]), pii{val, inf}) - list[node].begin() + left[node], right[node]);
int mid = cl + cr >> 1;
return query(l, r, val, 2 * node, cl, mid) + query(l, r, val, 2 * node + 1, mid + 1, cr);
}
void voidpoz(int poz, int val, int node = 1, int cl = 1, int cr = n) {
AIB::upd(lower_bound(all(list[node]), pii{val, 0}) - list[node].begin() + left[node], -val);
if(cl == cr)
return;
int mid = cl + cr >> 1;
if(poz <= mid)
voidpoz(poz, val, 2 * node, cl, mid);
else
voidpoz(poz, val, 2 * node + 1, mid + 1, cr);
return;
}
};
static void initdfs(int node) {
preord[inp] = node;
pin[node] = inp++;
for(auto x : g[node])
initdfs(x);
pout[node] = inp -1;
}
set<pii> elems[nmax];
static void dfs(int node) {
//cerr << node << ' ' << "amog\n";
for(auto x : g[node]) {
dfs(x);
if(elems[node].size() < elems[x].size())
swap(elems[x], elems[node]);
for(auto a : elems[x])
elems[node].insert(a);
}
//cerr << "amog\n";
int discrept = vec[node].second - AINT::query(pin[node], pout[node], vec[node].first);
//cerr << node + 1 << ":\n";
//cerr << AINT::query(pin[node], pout[node], vec[node].first) << ' ' << vec[node].second << ' ' << discrept << '\n';
if(discrept >= 0) {
//cerr << "sus\n";
while(elems[node].size() && elems[node].rbegin() -> first > vec[node].first) {
AINT::voidpoz(pin[elems[node].rbegin() -> second], vec[elems[node].rbegin() -> second].second);
//cerr << "ok\n";
elems[node].erase(*elems[node].rbegin());
}
elems[node].insert({vec[node].first, node});
//cerr << "amogus\n";
}
else
//cerr << "susy\n",
AINT::voidpoz(pin[node], vec[node].second);
//cerr << "ok\n";
//cerr << "amogii\n";
//for(auto [a, b] : elems[node])
//cerr << b << ' ' << vec[b].first << ' ' << vec[b].second << '\n';
//cerr << "amog\n";
return;
}
int main() {
cin >> n >> m >> k;
for(int i = 0; i < n; i++) {
vec[i] = pii{inf, 0};
}
AINT::initAIB();
for(int x, i = 1; i < n; i++) {
cin >> x;
g[--x].push_back(i);
}
for(int i = 0, v, d, w; i < m; i++)
cin >> v >> d >> w,
vec[--v] = pii{d, w};
initdfs(0);
AINT::initAINT();
dfs(0);
cout << AINT::query(1, n, -1) << '\n';
}
Compilation message
magictree.cpp: In function 'void AINT::initAIB(int, int, int)':
magictree.cpp:46:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
46 | int mid = cl + cr >> 1;
| ~~~^~~~
magictree.cpp: In function 'void AINT::initAINT(int, int, int)':
magictree.cpp:56:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
56 | int mid = cl + cr >> 1;
| ~~~^~~~
magictree.cpp:60:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | while(p[0] < list[l].size()) {
| ~~~~~^~~~~~~~~~~~~~~~
magictree.cpp:67:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | while(p[1] < list[r].size())
| ~~~~~^~~~~~~~~~~~~~~~
magictree.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int i = 0; i < list[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~
magictree.cpp: In function 'int AINT::query(int, int, int, int, int, int)':
magictree.cpp:78:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
78 | int mid = cl + cr >> 1;
| ~~~^~~~
magictree.cpp: In function 'void AINT::voidpoz(int, int, int, int, int)':
magictree.cpp:85:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
85 | int mid = cl + cr >> 1;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
16724 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
16724 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
110 ms |
71288 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
17156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
168 ms |
72728 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
16724 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
16724 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
27852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
16724 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
16724 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
16724 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
16724 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
