# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
41115 | wzy | Biochips (IZhO12_biochips) | C++14 | 316 ms | 419320 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pii pair<int,int>
#define ieps (int) 1e6
#define eps (int) 1e9
#define mp make_pair
#define pb push_back
vector<int> adj[ieps];
int dp[200005][505] ,n , m;
int label[ieps] , root;
int rvst[ieps];
int st[ieps] , ed[ieps] , t = 0;
void dfs(int x , int y){
rvst[t] = x;
st[x] = t++;
for(int i = 0 ; i < adj[x].size() ; i++){
int v = adj[x][i];
if(v == y) continue;
dfs(v,x);
}
ed[x] = t;
}
int solve(int i , int j){
if(dp[i][j] != -1) return dp[i][j];
dp[i][j] = 0;
if(i > t) return -eps;
if(i == t && j == m){
return 0;
}
if(i == t) return -eps;
return dp[i][j] = max(solve(i + 1 , j) , solve(ed[rvst[i]] + 1 , j + 1) + label[rvst[i]]);
}
int32_t main(){
scanf("%d%d" , &n , &m);
for(int i = 0 ; i < n; i++){
int y , x;
scanf("%d%d" , &y , &x);
label[i] = x;
if(y==0){
root = i;
continue;
}
else{
y--;
adj[i].pb(y);
adj[y].pb(i);
}
}
memset(dp , -1 , sizeof dp);
dfs(root, root);
printf("%d\n" , solve(0 , 0));
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |