#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef long long ll;
ll n,m,k,par[100005],niv[100005],dp[100005][3],val[100005],day[100005],minim[100005];
vector<int> muchii[100005];
struct date
{
ll nod,day,val;
} v[100005];
void dfscontrol(int nod)
{
if(nod==1)
niv[nod]=1;
for(int i=0;i<muchii[nod].size();i++)
{
int fiu=muchii[nod][i];
par[fiu]=nod;
niv[fiu]=niv[nod]+1;
dfscontrol(fiu);
}
}
bool comp(date a, date b)
{
if(a.day!=b.day)
return a.day<b.day;
if(niv[a.nod]!=niv[b.nod])
return niv[a.nod]>niv[b.nod];
return 0;
}
bool comp1(date a, date b)
{
return a.nod>b.nod;
}
void solve3()
{
sort(v+1,v+m+1,comp1);
for(int i=1;i<=1e5;i++)
minim[i]=1e9;
int ans=0;
for(int i=1;i<=m;i++)
{
int val=v[i].day;
int st=0;
int dr=i-1;
int best=0;
while(st<=dr)
{
int mij=(st+dr)/2;
if(minim[mij]<=val)
{
best=mij;
st=mij+1;
}
else
dr=mij-1;
}
ans=max(ans,best+1);
minim[best+1]=min(minim[best+1],val*1LL);
}
cout<<ans<<'\n';
}
void dfs(int nod)
{
for(int i=0;i<muchii[nod].size();i++)
{
int fiu=muchii[nod][i];
dfs(fiu);
}
if(val[nod]!=0&&day[nod]!=0)
for(int i=day[nod];i<=day[nod];i++)
dp[nod][i]+=val[nod];
for(int i=0;i<muchii[nod].size();i++)
{
int fiu=muchii[nod][i];
for(int j=1;j<=k;j++)
dp[nod][j]+=dp[fiu][j];
}
dp[nod][2]=max(dp[nod][1],dp[nod][2]);
}
void solve4()
{
for(int i=1;i<=m;i++)
{
int nod=v[i].nod;
day[nod]=v[i].day;
val[nod]=v[i].val;
}
dfs(1);
cout<<max(dp[1][1],dp[1][k])<<'\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>k;
bool is3=1;
for(int i=2;i<=n;i++)
{
int p;
cin>>p;
par[i]=p;
if(par[i]!=i-1)
is3=0;
muchii[p].push_back(i);
}
for(int i=1;i<=m;i++)
cin>>v[i].nod>>v[i].day>>v[i].val;
dfscontrol(1);
sort(v+1,v+m+1,comp);
if(k<=2)
{
solve4();
return 0;
}
if(is3)
{
solve3();
return 0;
}
for(int i=1;i<=m;i++)
{
int nod=v[i].nod;
ll x=v[i].val;
dp[nod][1]=dp[nod][0]+x;
while(nod!=1)
{
nod=par[nod];
dp[nod][0]+=x;
if(dp[nod][0]-x<=dp[nod][1]&&dp[nod][0]>dp[nod][1])
x=dp[nod][0]-dp[nod][1];
else if(dp[nod][0]<=dp[nod][1])
{
x=0;
break;
}
}
}
cout<<dp[1][0];
return 0;
}
Compilation message
magictree.cpp: In function 'void dfscontrol(int)':
magictree.cpp:15:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for(int i=0;i<muchii[nod].size();i++)
| ~^~~~~~~~~~~~~~~~~~~
magictree.cpp: In function 'void dfs(int)':
magictree.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i=0;i<muchii[nod].size();i++)
| ~^~~~~~~~~~~~~~~~~~~
magictree.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int i=0;i<muchii[nod].size();i++)
| ~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2636 KB |
Output is correct |
2 |
Correct |
1 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
1 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
3404 KB |
Output is correct |
6 |
Correct |
2 ms |
3404 KB |
Output is correct |
7 |
Correct |
2 ms |
3404 KB |
Output is correct |
8 |
Correct |
1 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
8576 KB |
Output is correct |
2 |
Correct |
1878 ms |
10584 KB |
Output is correct |
3 |
Correct |
63 ms |
9312 KB |
Output is correct |
4 |
Correct |
58 ms |
9176 KB |
Output is correct |
5 |
Execution timed out |
2078 ms |
9720 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3532 KB |
Output is correct |
2 |
Correct |
2 ms |
3532 KB |
Output is correct |
3 |
Correct |
2 ms |
3532 KB |
Output is correct |
4 |
Correct |
53 ms |
13068 KB |
Output is correct |
5 |
Correct |
50 ms |
12996 KB |
Output is correct |
6 |
Correct |
74 ms |
12960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
68 ms |
11844 KB |
Output is correct |
2 |
Correct |
92 ms |
11844 KB |
Output is correct |
3 |
Correct |
77 ms |
14620 KB |
Output is correct |
4 |
Correct |
38 ms |
10692 KB |
Output is correct |
5 |
Correct |
55 ms |
18060 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2636 KB |
Output is correct |
2 |
Correct |
1 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
1 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
3404 KB |
Output is correct |
6 |
Correct |
2 ms |
3404 KB |
Output is correct |
7 |
Correct |
2 ms |
3404 KB |
Output is correct |
8 |
Correct |
1 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
62 ms |
10256 KB |
Output is correct |
11 |
Correct |
65 ms |
10300 KB |
Output is correct |
12 |
Correct |
1258 ms |
12228 KB |
Output is correct |
13 |
Correct |
35 ms |
9128 KB |
Output is correct |
14 |
Correct |
62 ms |
12852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
3736 KB |
Output is correct |
2 |
Correct |
38 ms |
7896 KB |
Output is correct |
3 |
Correct |
29 ms |
7920 KB |
Output is correct |
4 |
Correct |
25 ms |
8012 KB |
Output is correct |
5 |
Correct |
9 ms |
6604 KB |
Output is correct |
6 |
Correct |
41 ms |
8460 KB |
Output is correct |
7 |
Correct |
44 ms |
10128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2636 KB |
Output is correct |
2 |
Correct |
1 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
1 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
3404 KB |
Output is correct |
6 |
Correct |
2 ms |
3404 KB |
Output is correct |
7 |
Correct |
2 ms |
3404 KB |
Output is correct |
8 |
Correct |
1 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
2 ms |
3532 KB |
Output is correct |
11 |
Correct |
2 ms |
3532 KB |
Output is correct |
12 |
Correct |
2 ms |
3532 KB |
Output is correct |
13 |
Correct |
53 ms |
13068 KB |
Output is correct |
14 |
Correct |
50 ms |
12996 KB |
Output is correct |
15 |
Correct |
74 ms |
12960 KB |
Output is correct |
16 |
Correct |
62 ms |
10256 KB |
Output is correct |
17 |
Correct |
65 ms |
10300 KB |
Output is correct |
18 |
Correct |
1258 ms |
12228 KB |
Output is correct |
19 |
Correct |
35 ms |
9128 KB |
Output is correct |
20 |
Correct |
62 ms |
12852 KB |
Output is correct |
21 |
Correct |
18 ms |
4172 KB |
Output is correct |
22 |
Correct |
66 ms |
9256 KB |
Output is correct |
23 |
Correct |
49 ms |
9296 KB |
Output is correct |
24 |
Correct |
62 ms |
10244 KB |
Output is correct |
25 |
Correct |
40 ms |
9188 KB |
Output is correct |
26 |
Correct |
1402 ms |
10552 KB |
Output is correct |
27 |
Correct |
938 ms |
12128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2636 KB |
Output is correct |
2 |
Correct |
1 ms |
2636 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
1 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
3404 KB |
Output is correct |
6 |
Correct |
2 ms |
3404 KB |
Output is correct |
7 |
Correct |
2 ms |
3404 KB |
Output is correct |
8 |
Correct |
1 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
35 ms |
8576 KB |
Output is correct |
11 |
Correct |
1878 ms |
10584 KB |
Output is correct |
12 |
Correct |
63 ms |
9312 KB |
Output is correct |
13 |
Correct |
58 ms |
9176 KB |
Output is correct |
14 |
Execution timed out |
2078 ms |
9720 KB |
Time limit exceeded |