Submission #701646

#TimeUsernameProblemLanguageResultExecution timeMemory
701646hgmhcBiochips (IZhO12_biochips)C++17
100 / 100
475 ms22348 KiB
#include <bits/stdc++.h> using namespace std; using ii = pair<int,int>; using ll = long long; #define rep(i,a,b) for (auto i = (a); i <= (b); ++i) #define per(i,a,b) for (auto i = (b); i >= (a); --i) #define all(x) begin(x), end(x) #define siz(x) int((x).size()) #define Mup(x,y) x = max(x,y) #define mup(x,y) x = min(x,y) #define fi first #define se second #define dbg(...) fprintf(stderr,__VA_ARGS__) const int N = 2e5+3, M = 503; int n, m, a[N], r, sub[N]; vector<int> child[N]; vector<ll> dp[N]; void pre(int s = r, int e = 0) { sub[s] = 1; for (auto u : child[s]) if (u != e) { pre(u,s), sub[s] += sub[u]; } } void solve(int s = r, int e = 0) { dp[s].resize(min(m,sub[s])+1,-1e18); dp[s][0] = 0; for (auto u : child[s]) if (u != e) { solve(u,s); per(x,1,min(m,sub[s])) rep(y,0,min(x,sub[u])) { Mup(dp[s][x],dp[u][y]+dp[s][x-y]); } } Mup(dp[s][1],ll(a[s])); } int main() { scanf("%d %d", &n, &m); rep(i,1,n) { int p; scanf("%d %d", &p, &a[i]); if (p == 0) r = i; else child[p].push_back(i); } pre(), solve(); printf("%lld", dp[r][m]); }

Compilation message (stderr)

biochips.cpp: In function 'int main()':
biochips.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
biochips.cpp:39:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         int p; scanf("%d %d", &p, &a[i]);
      |                ~~~~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...