Submission #339097

#TimeUsernameProblemLanguageResultExecution timeMemory
339097fixikmilaBiochips (IZhO12_biochips)C++14
0 / 100
2068 ms152192 KiB
#include <bits/stdc++.h> #ifndef LOCAL_RUN #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("fast-math") #pragma GCC target("avx2,tune=native") #endif using namespace std; #define MOD 1000000007 typedef long long ll; typedef pair<ll,ll>pll; typedef long double ld; ll bin_pow(ll a,ll b){ if(b==0)return 1; if(b%2==0){ ll t=bin_pow(a,b/2); return t*t%MOD; } else return a*bin_pow(a,b-1)%MOD; } vector<ll>graph[200000]; int dp[200000][501],a[200000]; bool used[200000]; int t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0; void dfs(ll v,ll p=-1){ used[v]=true; if(graph[v].size()==1){ dp[v][1]=a[v]; return; } for(auto u : graph[v]){ if(used[u])continue; dfs(u,v); } for(auto u : graph[v]){ if(u==p)continue; vector<ll>c(m+1); for(int j=0;j<=m;j++){ for(int i=j;i<=m;i++){ //if(v==2&&u==4&&i==2)cout<<j<<" "<<dp[4][1]<<dp[2]<<"ss"<<endl; c[i]=max(ll(dp[v][i-j]+dp[u][j]),c[i]); } } for(int z=m;z>=0;z--){ dp[v][z]=c[z]; } } dp[v][1]=a[v]; for(auto u : graph[v]){ if(u==p)continue; dp[v][1]=max(dp[v][1],dp[u][1]); } } int main() { //freopen("stones.in","r",stdin); //freopen("stones.out","w",stdout); ios::sync_with_stdio(false); cin.tie(0); string s; cin>>n>>m; for(int i=0;i<n;i++){ cin>>x>>y; x--; a[i]=y; if(x==-1){ z=i; continue; } graph[i].push_back(x); graph[x].push_back(i); } dfs(z); ans=dp[z][m]; //cout<<dp[2][2]<<endl; cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...