#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=200005;
vector<int> v[nmax];
int dp[2][nmax];
int rep[nmax],l[nmax],r[nmax],val[nmax];
int n,m,i,j,nr,tt,x,use;
void dfs(int x)
{
rep[++nr]=x;l[x]=nr;
for(int i=0;i<v[x].size();i++)
dfs(v[x][i]);
r[x]=nr;
}
int main()
{
// freopen("data.in","r",stdin);
ios_base::sync_with_stdio(false);
cin>>n>>m;
for(i=1;i<=n;i++)
{
cin>>tt>>val[i];
v[tt].push_back(i);
}
dfs(v[0][0]);
for(i=0;i<=m;i++)
{
use=1-use;
for(j=0;j<=n;j++)
dp[1-use][j]=-(1<<30);
for(j=1;j<=n;j++)
{
x=rep[j];
dp[use][j]=max(dp[use][j],dp[use][j-1]);
dp[1-use][r[x]]=max(dp[use][l[x]-1]+val[x],dp[1-use][r[x]]);
}
}
cout<<dp[use][n];
return 0;
}
Compilation message
biochips.cpp: In function 'void dfs(int)':
biochips.cpp:13:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
biochips.cpp: In function 'int main()':
biochips.cpp:31:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for(j=0;j<=n;j++)
^~~
biochips.cpp:33:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for(j=1;j<=n;j++)
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5236 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5284 KB |
Output is correct |
| 4 |
Correct |
13 ms |
5612 KB |
Output is correct |
| 5 |
Correct |
15 ms |
5704 KB |
Output is correct |
| 6 |
Correct |
16 ms |
5976 KB |
Output is correct |
| 7 |
Correct |
458 ms |
11596 KB |
Output is correct |
| 8 |
Correct |
481 ms |
13080 KB |
Output is correct |
| 9 |
Correct |
457 ms |
15052 KB |
Output is correct |
| 10 |
Correct |
660 ms |
17088 KB |
Output is correct |
