#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int MAXN=2e5+7;
#pragma optimize ("O3")
#pragma target ("sse4")
#define endl '\n'
#define getchar getchar_unlocked
struct Node {
long long mx, lazyadd, lazyset;
};
vector <int> v[MAXN];
set <int> vals;
vector <pair <int, long long> > dp[MAXN];
Node tree[4*MAXN];
long long c[MAXN];
int h[MAXN], cnt;
pair <int,int> kopie[MAXN];
int ss[MAXN];
void merge_lazy(int par, int ch) {
if (tree[par].lazyset!=-1) {
tree[ch].lazyset=tree[par].lazyset;
tree[ch].lazyadd=0;
return;
}
if (tree[ch].lazyset==-1) tree[ch].lazyadd+=tree[par].lazyadd;
else tree[ch].lazyset+=tree[par].lazyadd;
}
void push_lazy(int node, int l, int r) {
if (tree[node].lazyadd==0 && tree[node].lazyset==-1) return;
if (tree[node].lazyadd==0) tree[node].mx=tree[node].lazyset;
else tree[node].mx+=tree[node].lazyadd;
if (l!=r) {
merge_lazy(node,node*2);
merge_lazy(node,node*2+1);
}
tree[node].lazyadd=0;
tree[node].lazyset=-1;
}
void add_update(int node, int l, int r, int ql, int qr, long long ch) {
if (ql>r || qr<l) return;
push_lazy(node,l,r);
if (l>=ql && r<=qr) {
tree[node].lazyadd=ch;
push_lazy(node,l,r);
return;
}
int mid=(l+r)/2;
add_update(node*2,l,mid,ql,qr,ch);
add_update(node*2+1,mid+1,r,ql,qr,ch);
tree[node].mx=max(tree[node*2].mx,tree[node*2+1].mx);
}
void set_update(int node, int l, int r, int ql, int qr, long long ch) {
if (ql>r || qr<l) return;
push_lazy(node,l,r);
if (l>=ql && r<=qr) {
tree[node].lazyset=ch;
push_lazy(node,l,r);
return;
}
int mid=(l+r)/2;
set_update(node*2,l,mid,ql,qr,ch);
set_update(node*2+1,mid+1,r,ql,qr,ch);
tree[node].mx=max(tree[node*2].mx,tree[node*2+1].mx);
}
long long query(int node, int l, int r, int qind) {
push_lazy(node,l,r);
if (l==r) return tree[node].mx;
int mid=(l+r)/2;
if (qind<=mid) return query(node*2,l,mid,qind);
return query(node*2+1,mid+1,r,qind);
}
int find_ind(int node, int l, int r, int ql, int qr, long long ch) {
if (ql>r || qr<l) return -1;
push_lazy(node,l,r);
if (tree[node].mx<=ch) return -1;
if (l==r) return l;
int mid=(l+r)/2;
int res=find_ind(node*2,l,mid,ql,qr,ch);
if (res!=-1) return res;
return find_ind(node*2+1,mid+1,r,ql,qr,ch);
}
void find_ss(int x) {
ss[x]=1;
for (int i=0;i<v[x].size();++i) {
find_ss(v[x][i]);
ss[x]+=ss[v[x][i]];
}
for (int i=1;i<v[x].size();++i) {
if (ss[v[x][i]]>ss[v[x][0]]) swap(v[x][0],v[x][i]);
}
}
void find_dp(int x) {
if (v[x].empty()) {
add_update(1,1,cnt,h[x]+1,cnt,c[x]);
vals.insert(h[x]);
vals.insert(cnt);
return;
}
long long cur_res;
int k;
cur_res=0;
for (int i=1;i<v[x].size();++i) {
find_dp(v[x][i]);
dp[v[x][i]].resize(vals.size());
k=0;
for (auto j:vals) {
dp[v[x][i]][k]={j,query(1,1,cnt,j)};
k++;
}
cur_res+=query(1,1,cnt,(*vals.lower_bound(h[x])));
set_update(1,1,cnt,1,cnt,0);
vals.clear();
}
find_dp(v[x][0]);
cur_res+=query(1,1,cnt,(*vals.lower_bound(h[x])));
for (int i=1;i<v[x].size();++i) {
for (int j=0;j<dp[v[x][i]].size();) {
int newv=dp[v[x][i]][j].first;
set_update(1,1,cnt,newv,newv, query(1,1,cnt, (*vals.lower_bound(newv)) ) );
}
}
for (int i=1;i<v[x].size();++i) {
int ch=v[x][i];
for (int j=0;j<dp[ch].size();++j) {
if (j==0) add_update(1,1,cnt,1,dp[ch][j].first,dp[ch][j].second);
else {
add_update(1,1,cnt,dp[ch][j-1].first+1,dp[ch][j].first,dp[ch][j].second);
}
vals.insert(dp[ch][j].first);
}
}
add_update(1,1,cnt,1,cnt,c[x]);
int pos=find_ind(1,1,cnt,1,h[x],cur_res);
if (pos!=-1) {
set_update(1,1,cnt,pos,h[x],cur_res);
}
vals.insert(h[x]);
}
int read() {
int res=0;
char c=getchar();
while (c<'0' || c>'9') c=getchar();
while (c>='0' && c<='9') {
res=res*10+c-'0';
c=getchar();
}
return res;
}
int main () {
int n, par;
n=read();
for (int i=1;i<=n;++i) {
par=read();
h[i]=read();
c[i]=read();
if (i!=1) v[par].push_back(i);
kopie[i].first=h[i];
kopie[i].second=i;
}
sort(kopie+1,kopie+n+1);
cnt=0;
for (int i=1;i<=n;++i) {
if (kopie[i].first!=kopie[i-1].second) cnt++;
h[kopie[i].second]=cnt;
}
cnt++;
find_ss(1);
for (int j=1;j<=4*cnt;++j) {
tree[j].lazyset=-1;
}
find_dp(1);
cout << query(1,1,cnt,1) << endl;
return 0;
}
/*
6
1 6 5
1 3 6
1 8 4
3 4 9
2 2 5
2 5 6
*/
Compilation message
worst_reporter2.cpp:7: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
7 | #pragma optimize ("O3")
|
worst_reporter2.cpp:8: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
8 | #pragma target ("sse4")
|
worst_reporter2.cpp: In function 'void find_ss(int)':
worst_reporter2.cpp:101:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for (int i=0;i<v[x].size();++i) {
| ~^~~~~~~~~~~~
worst_reporter2.cpp:105:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for (int i=1;i<v[x].size();++i) {
| ~^~~~~~~~~~~~
worst_reporter2.cpp: In function 'void find_dp(int)':
worst_reporter2.cpp:120:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for (int i=1;i<v[x].size();++i) {
| ~^~~~~~~~~~~~
worst_reporter2.cpp:138:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for (int i=1;i<v[x].size();++i) {
| ~^~~~~~~~~~~~
worst_reporter2.cpp:139:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for (int j=0;j<dp[v[x][i]].size();) {
| ~^~~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:145:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for (int i=1;i<v[x].size();++i) {
| ~^~~~~~~~~~~~
worst_reporter2.cpp:147:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for (int j=0;j<dp[ch].size();++j) {
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
16732 KB |
Output is correct |
| 2 |
Correct |
5 ms |
16476 KB |
Output is correct |
| 3 |
Execution timed out |
2080 ms |
16720 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
16732 KB |
Output is correct |
| 2 |
Correct |
5 ms |
16476 KB |
Output is correct |
| 3 |
Execution timed out |
2080 ms |
16720 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
16732 KB |
Output is correct |
| 2 |
Correct |
5 ms |
16476 KB |
Output is correct |
| 3 |
Execution timed out |
2080 ms |
16720 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
