#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#define ll long long
using namespace std;
struct Node{
ll chl = -1;
ll chr = -1;
ll val = 0;
ll lazy = 0;
};
vector <Node> st;
vector <ll> U;
ll n, f, cnt, A[200000], H[200000], C[200000], in[200000];
queue <ll> Q;
map <ll, ll> mp;
struct SegTree{
ll get(ll u) {
if (u == -1) {
st.push_back({-1, -1, 0});
return st.size()-1;
}
return u;
}
ll rt = -1;
void init() {
rt = get(rt);
}
void push(ll id) {
if (st[id].chl != -1) {
st[st[id].chl].val += st[id].lazy;
st[st[id].chl].lazy += st[id].lazy;
}
if (st[id].chr != -1) {
st[st[id].chr].val += st[id].lazy;
st[st[id].chr].lazy += st[id].lazy;
}
st[id].lazy = 0;
}
ll query(ll id, ll l, ll r, ll ql, ll qr) {
if (id == -1 || qr < l || r < ql) return 0;
else if (ql <= l && r <= qr) return st[id].val;
push(id);
ll mid = (l+r)/2;
return max(query(st[id].chl, l, mid, ql, qr), query(st[id].chr, mid+1, r, ql, qr));
}
void push_up(ll id) {
st[id].val = max((st[id].chl != -1 ? st[st[id].chl].val : 0), (st[id].chr != -1 ? st[st[id].chr].val : 0));
}
void update(ll id, ll l, ll r, ll q, ll w) {
if (l == r) {
st[id].val = max(st[id].val, w);
return;
}
push(id);
ll mid = (l+r)/2;
if (q <= mid) {
st[id].chl = get(st[id].chl);
update(st[id].chl, l, mid, q, w);
}
else {
st[id].chr = get(st[id].chr);
update(st[id].chr, mid+1, r, q, w);
}
push_up(id);
}
ll wa, wb;
void init_merge(ll i, ll j) {
wa = wb = 0;
merge(i, j, 0, mp.size()-1);
}
void merge(ll a, ll b, ll l, ll r) {
push(a);
push(b);
ll mid = (l+r)/2, ta, tb;
//cout << l << " " << r << " " << "R" << " " << wa << " " << wb << endl;
if (st[a].chr != -1) ta = st[st[a].chr].val;
if (st[b].chr != -1) tb = st[st[b].chr].val;
if (st[a].chr != -1 && st[b].chr != -1) {
merge(st[a].chr, st[b].chr, mid+1, r);
}
if (st[a].chr != -1) wa = max(wa, ta);
if (st[b].chr != -1) wb = max(wb, tb);
if (st[a].chr == -1 && st[b].chr != -1) {
st[a].chr = st[b].chr;
st[st[a].chr].val += wa;
st[st[a].chr].lazy += wa;
}
else if (st[a].chr != -1 && st[b].chr == -1) {
st[st[a].chr].val += wb;
st[st[a].chr].lazy += wb;
}
if (st[a].chl != -1) ta = st[st[a].chl].val;
if (st[b].chl != -1) tb = st[st[b].chl].val;
if (st[a].chl != -1 && st[b].chl != -1) {
merge(st[a].chl, st[b].chl, l, mid);
}
//cout << l << " " << r << " " << "L" << " " << wa << " " << wb << endl;
if (st[a].chl != -1) wa = max(wa, ta);
if (st[b].chl != -1) wb = max(wb, tb);
if (st[a].chl == -1 && st[b].chl != -1) {
st[a].chl = st[b].chl;
st[st[a].chl].val += wa;
st[st[a].chl].lazy += wa;
}
else if (st[a].chl != -1 && st[b].chl == -1) {
st[st[a].chl].val += wb;
st[st[a].chl].lazy += wb;
}
//cout << st[a].val << " " << st[b].val << " ";
if (l != r) push_up(a);
else {
st[a].val += max(st[b].val, wb);
}
//cout << l << " " << r << " -> " << st[a].val << " " << wa << " " << wb << endl;
}
}ST[200000];
void dfs(ll i, ll id) {
--in[i];
U.push_back(i);
//cout << i+1 << endl;
/*auto tmp = ST[i].query(ST[i].rt, 0, mp.size()-1, H[i], mp.size()-1);
ST[i].update(ST[i].rt, 0, mp.size()-1, H[i], tmp+C[i]);
cout << i+1 << "*" << H[i] << " " << tmp+C[i] << endl;*/
if (id == -1) id = i;
else {
ST[id].init_merge(ST[id].rt, ST[i].rt);
//cout << ST[id].query(ST[id].rt, 0, mp.size()-1, 0, mp.size()-1) << "*\n";
}
if (in[A[i]]) {
dfs(A[i], id);
}
}
int main() {
cin >> n;
for (int i=0; i<n; ++i) {
cin >> A[i] >> H[i] >> C[i];
f += C[i];
--A[i];
//cout << A[i]+1 << " " << i+1 << endl;
++in[A[i]];
++mp[H[i]];
ST[i].init();
}
for (auto &[x, y] : mp) {
y = cnt++;
}
for (int i=0; i<n; ++i) {
H[i] = mp[H[i]];
if (!in[i]) Q.push(i);
}
while (!Q.empty()) {
auto u = Q.front();
Q.pop();
//cout << in[u] << endl;
//cout << A[u]+1 << " " << u+1 << endl;
auto tmp = ST[u].query(ST[u].rt, 0, mp.size()-1, H[u], mp.size()-1);
//cout << H[u] << " " << tmp << " " << tmp+C[u] << endl;
ST[u].update(ST[u].rt, 0, mp.size()-1, H[u], tmp+C[u]);
--in[A[u]];
if (!in[A[u]]) Q.push(A[u]);
ST[A[u]].init_merge(ST[A[u]].rt, ST[u].rt);
//cout << ST[A[u]].query(ST[A[u]].rt, 0, mp.size()-1, 0, mp.size()-1) << endl;
}
ll id = -1;
for (int i=0; i<n; ++i) {
if (in[i]) {
U.clear();
//cout << i+1 << endl;
dfs(i, -1);
//cout << ST[i].query(ST[i].rt, 0, mp.size()-1, 0, mp.size()-1) << endl;
sort(U.begin(), U.end(), [](auto a, auto b) {
return H[a] < H[b];
});
for (auto u : U) {
auto tmp = ST[i].query(ST[i].rt, 0, mp.size()-1, H[u], mp.size()-1);
ST[i].update(ST[i].rt, 0, mp.size()-1, H[u], tmp+C[u]);
//cout << i+1 << "*" << H[i] << " " << tmp+C[i] << endl;
}
f -= ST[i].query(ST[i].rt, 0, mp.size()-1, 0, mp.size()-1);
}
}
cout << f << '\n';
}
Compilation message
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:151:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
151 | for (auto &[x, y] : mp) {
| ^
worst_reporter2.cpp:171:6: warning: unused variable 'id' [-Wunused-variable]
171 | ll id = -1;
| ^~
worst_reporter2.cpp: In member function 'void SegTree::merge(long long int, long long int, long long int, long long int)':
worst_reporter2.cpp:79:23: warning: 'ta' may be used uninitialized in this function [-Wmaybe-uninitialized]
79 | ll mid = (l+r)/2, ta, tb;
| ^~
worst_reporter2.cpp:79:27: warning: 'tb' may be used uninitialized in this function [-Wmaybe-uninitialized]
79 | ll mid = (l+r)/2, ta, tb;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
10840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
10840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
10840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
