Submission #1206843

#TimeUsernameProblemLanguageResultExecution timeMemory
1206843em4ma2Biochips (IZhO12_biochips)C++20
0 / 100
199 ms401712 KiB
// اللهم صل على محمد وعلى ال محمد كما صليت على ابراهيم وعلى ال ابراهيم انك حميد مجيد #include "bits/stdc++.h" using namespace std; #define ll long long //#define int long long #define pb push_back #define applejuice ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); //const int mod=1e9+7; const int mod=998244353; const ll inf=1e17; const int mxsz=2e5+4; const int off=1<<20; const int siz=504; vector<int>adj[mxsz]; int vis[mxsz]; int a[mxsz]; int mx=0; int dp[mxsz][siz]; int sz[mxsz]; vector<int>res(mxsz); void dfs(int i){ vis[i]=1; for (auto x:adj[i]){ if (!vis[x]){ dfs(x); sz[i]+=sz[x]; } } } void tra(int i,int m){ vis[i]=1; if (adj[i].size()>1) { for (int km = 1; km < adj[i].size(); km++) { auto x = adj[i][km], y = adj[i][km - 1]; if (!vis[x]) { fill(res.begin(), res.end(), 0); for (int j = 1; j <= sz[x]; j++) { for (int l = 1; l <= sz[y]; l++) { res[i + j] = max(res[i + j], a[i] + a[j]); } } dp[i][m] = res[m]; dfs(x); } } }else{ for (auto x:adj[i]){ if (!vis[x]){ dp[i][m]=max(dp[x][m],a[i]); dfs(x); } } } } signed main(){ applejuice; int n,m; cin>>n>>m; int root; for (int i=1;i<=n;i++){ int p, x; cin>>p>>x; a[i]=x; if (p==0)root=i; adj[p].pb(i); } for (int i=0;i<=n;i++){ for (int j=0;j<=m;j++){ dp[i][j]=-1; } } int abs=0,sum; for (int i=1;i<=n;i++){ if (adj[i].size()==0){ dp[i][1]=a[i]; } } for (int i=1;i<=n;i++){ sz[i]=1; } dfs(root); for (int i=1;i<=n;i++)vis[i]=0; tra(root,m); cout<<dp[root][m]<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...