#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set>
typedef long long llong;
const int MAXN = 200000 + 10;
const llong INF = 1e18;
const int INTINF = 1e9;
int n;
struct SegmentTree
{
struct Node
{
llong max;
llong lazyAdd;
llong lazySet;
Node()
{
max = 0;
lazyAdd = 0;
lazySet = -1;
}
friend Node operator + (const Node &left, const Node &right)
{
Node res;
res.max = std::max(left.max, right.max);
return res;
}
};
Node tree[4*MAXN];
void mergeLazys(Node &to, Node from)
{
if (from.lazySet != -1)
{
to.lazySet = from.lazySet;
to.lazyAdd = 0;
return;
}
if (to.lazySet != -1)
{
to.lazySet += from.lazyAdd;
} else
{
to.lazyAdd += from.lazyAdd;
}
}
void push(int node, int l, int r)
{
if (tree[node].lazyAdd == 0 && tree[node].lazySet == -1)
{
return;
}
assert(tree[node].lazyAdd == 0 || tree[node].lazySet == -1);
if (tree[node].lazyAdd == 0)
{
tree[node].max = tree[node].lazySet;
} else
{
tree[node].max += tree[node].lazyAdd;
}
if (l < r)
{
mergeLazys(tree[2*node], tree[node]);
mergeLazys(tree[2*node + 1], tree[node]);
}
tree[node].lazyAdd = 0;
tree[node].lazySet = -1;
}
// void resetUpdate(int l, int r, int node, int queryPos)
// {
// push(node, l, r);
// if (queryPos < l || r < queryPos)
// {
// return;
// }
// if (l == r)
// {
// tree[node] = Node();
// return;
// }
// int mid = (l + r) / 2;
// resetUpdate(l, mid, 2*node, queryPos);
// resetUpdate(mid + 1, r, 2*node + 1, queryPos);
// tree[node] = tree[2*node] + tree[2*node + 1];
// }
// void addUpdate(int l, int r, int node, int queryL, int queryR, llong queryVal)
// {
// push(node, l, r);
// if (queryR < l || r < queryL)
// {
// return;
// }
// if (queryL <= l && r <= queryR)
// {
// tree[node].lazyAdd = queryVal;
// push(node, l, r);
// return;
// }
// int mid = (l + r) / 2;
// addUpdate(l, mid, 2*node, queryL, queryR, queryVal);
// addUpdate(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
// tree[node] = tree[2*node] + tree[2*node + 1];
// }
void addUpdate(int l, int r, int node, int queryL, int queryR, llong queryVal)
{
push(node, l, r);
if (queryR < l || r < queryL)
{
return;
}
if (queryL <= l && r <= queryR)
{
tree[node].lazyAdd = queryVal;
push(node, l, r);
return;
}
int mid = (l + r) / 2;
addUpdate(l, mid, 2*node, queryL, queryR, queryVal);
addUpdate(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
tree[node] = tree[2*node] + tree[2*node + 1];
}
void setUpdate(int l, int r, int node, int queryL, int queryR, llong queryVal)
{
push(node, l, r);
if (queryR < l || r < queryL)
{
return;
}
if (queryL <= l && r <= queryR)
{
tree[node].lazySet = queryVal;
push(node, l, r);
return;
}
int mid = (l + r) / 2;
setUpdate(l, mid, 2*node, queryL, queryR, queryVal);
setUpdate(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
tree[node] = tree[2*node] + tree[2*node + 1];
}
llong pointQuery(int l, int r, int node, int queryPos)
{
push(node, l, r);
if (l == r)
{
return tree[node].max;
}
int mid = (l + r) / 2;
if (queryPos <= mid) return pointQuery(l, mid, 2*node, queryPos);
else return pointQuery(mid + 1, r, 2*node + 1, queryPos);
}
int query(int l, int r, int node, int queryL, int queryR, llong queryVal)
{
push(node, l, r);
if (queryR < l || r < queryL || tree[node].max <= queryVal)
{
return n + 1;
}
if (l == r)
{
return l;
}
int mid = (l + r) / 2;
int res = query(l, mid, 2*node, queryL, queryR, queryVal);
if (res != n + 1) return res;
return query(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
}
// void resetUpdate(int pos)
// {
// update(1, n, 1, pos);
// }
void reset()
{
setUpdate(1, n + 1, 1, 1, n + 1, 0);
}
void addUpdate(int l, int r, llong val)
{
addUpdate(1, n + 1, 1, l, r, val);
}
void setUpdate(int l, int r, llong val)
{
setUpdate(1, n + 1, 1, l, r, val);
}
llong pointQuery(int pos)
{
return pointQuery(1, n + 1, 1, pos);
}
int query(int l, int r, llong val)
{
return query(1, n + 1, 1, l, r, val);
}
};
int h[MAXN];
int c[MAXN];
int sz[MAXN];
int perm[MAXN];
SegmentTree tree;
std::vector <int> g[MAXN];
std::set <int> vals[MAXN];
std::vector <llong> dp[MAXN];
void buildDFS(int node)
{
sz[node] = 1;
for (const int &u : g[node])
{
buildDFS(u);
sz[node] += sz[u];
}
for (int i = 1 ; i < g[node].size() ; ++i)
{
if (sz[g[node][i]] > sz[g[node][0]])
{
std::swap(g[node][i], g[node][0]);
}
}
}
void solveDFS(int node)
{
if (g[node].empty())
{
vals[node].insert(n + 1);
vals[node].insert(h[node]);
tree.addUpdate(h[node] + 1, n + 1, c[node]);
// std::cout << "dp vals: " << node << ":\n";
// for (const int &val : vals[node])
// {
// std::cout << val << " = " << tree.pointQuery(val) << '\n';
// }
return;
}
llong res = 0;
for (int i = 1 ; i < g[node].size() ; ++i)
{
int u = g[node][i];
solveDFS(u);
dp[u].reserve(vals[u].size());
for (const int &val : vals[u])
{
dp[u].push_back(tree.pointQuery(val));
}
auto it = vals[u].lower_bound(h[u]);
res += tree.pointQuery(*it);
tree.reset();
}
solveDFS(g[node][0]);
vals[node] = std::move(vals[g[node][0]]);
auto it = vals[node].lower_bound(h[node]);
res += tree.pointQuery(*it);
for (int i = 1 ; i < g[node].size() ; ++i)
{
int u = g[node][i];
for (const int &newVal : vals[u])
{
tree.setUpdate(newVal, newVal, tree.pointQuery(*vals[node].lower_bound(newVal)));
}
}
for (int i = 1 ; i < g[node].size() ; ++i)
{
int u = g[node][i];
assert(vals[u].size());
int first = *vals[u].begin();
tree.addUpdate(1, first, dp[u][0]);
auto it = std::next(vals[u].begin());
for (int idx = 1 ; it != vals[u].end() ; ++idx, ++it)
{
tree.addUpdate(*std::prev(it) + 1, *it, dp[u][idx]);
}
for (const int &val : vals[u])
{
vals[node].insert(val);
}
}
tree.addUpdate(1, n + 1, c[node]);
int firstPos = tree.query(1, h[node], res);
if (firstPos != n + 1)
{
assert(firstPos <= h[node]);
tree.setUpdate(firstPos, h[node], res);
}
vals[node].insert(h[node]);
// std::cout << "res is: " << res << '\n';
// std::cout << "dp vals: " << node << ":\n";
// for (const int &val : vals[node])
// {
// std::cout << val << " = " << tree.pointQuery(val) << '\n';
// }
}
void solve()
{
std::iota(perm + 1, perm + 1 + n, 1);
std::sort(perm + 1, perm + 1 + n, [&](int x, int y)
{
return h[x] < h[y];
});
int cnt = 0;
int last = 0;
for (int i = 1 ; i <= n ; ++i)
{
cnt += (h[perm[i]] > last);
last = h[perm[i]];
h[perm[i]] = cnt;
}
buildDFS(1);
solveDFS(1);
std::cout << tree.pointQuery(1) << '\n';
}
void input()
{
std::cin >> n;
for (int i = 1 ; i <= n ; ++i)
{
int par;
std::cin >> par >> h[i] >> c[i];
if (i != 1) g[par].push_back(i);
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
return 0;
}
Compilation message
worst_reporter2.cpp: In function 'void buildDFS(int)':
worst_reporter2.cpp:250:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
250 | for (int i = 1 ; i < g[node].size() ; ++i)
| ~~^~~~~~~~~~~~~~~~
worst_reporter2.cpp: In function 'void solveDFS(int)':
worst_reporter2.cpp:277:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
277 | for (int i = 1 ; i < g[node].size() ; ++i)
| ~~^~~~~~~~~~~~~~~~
worst_reporter2.cpp:298:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
298 | for (int i = 1 ; i < g[node].size() ; ++i)
| ~~^~~~~~~~~~~~~~~~
worst_reporter2.cpp:307:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
307 | for (int i = 1 ; i < g[node].size() ; ++i)
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
39512 KB |
Output is correct |
| 2 |
Correct |
7 ms |
39516 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
39516 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
39512 KB |
Output is correct |
| 2 |
Correct |
7 ms |
39516 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
39516 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
39512 KB |
Output is correct |
| 2 |
Correct |
7 ms |
39516 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
39516 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
