Submission #31935

#TimeUsernameProblemLanguageResultExecution timeMemory
31935kazelBiochips (IZhO12_biochips)C++14
100 / 100
149 ms21576 KiB
#include<bits/stdc++.h> using namespace std; int val[200001], m; vector<int> g[200001], dp[200001]; void dfs(int c) { if(g[c].empty()) { dp[c].push_back(val[c]); return; } priority_queue<tuple<int,int,int>> pq; for(int e : g[c]) { dfs(e); pq.emplace(dp[e][0],e,1); } int v = 0; for(int t=0;t<m;t++) { if(pq.empty()) break; int x,y,z; tie(x,y,z) = pq.top(); pq.pop(); v += x; dp[c].push_back(v); if(dp[y].size()<=z) continue; x = dp[y][z]-dp[y][z-1]; pq.emplace(x,y,z+1); } if(dp[c][0] < val[c]) dp[c][0] = val[c]; for(int e : g[c]) dp[e].clear(); } int main() { int n, r; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { int p; scanf("%d%d",&p,val+i); if(!p) r = i; else g[p].push_back(i); } dfs(r); printf("%d\n",dp[r][m-1]); }

Compilation message (stderr)

biochips.cpp: In function 'void dfs(int)':
biochips.cpp:29:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(dp[y].size()<=z) continue;
                        ^
biochips.cpp: In function 'int main()':
biochips.cpp:40:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
biochips.cpp:44:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&p,val+i);
                               ^
biochips.cpp:49:28: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
     printf("%d\n",dp[r][m-1]);
                            ^
#Verdict Execution timeMemoryGrader output
Fetching results...