Submission #21868

#TimeUsernameProblemLanguageResultExecution timeMemory
21868ulnaBiochips (IZhO12_biochips)C++11
100 / 100
446 ms444604 KiB
#include <bits/stdc++.h> using namespace std; // why am I so weak int n, m; int x[200055]; vector<int> g[200055]; int t, dfn[200055], r[200055]; int dp[200055][555]; void dfs(int v) { dfn[v] = t++; for (auto u : g[v]) { dfs(u); } r[v] = t; } int main() { scanf("%d %d", &n, &m); int root = -1; for (int i = 0; i < n; i++) { int a, b; scanf("%d %d", &a, &b); a--; x[i] = b; if (~a) g[a].push_back(i); else root = i; } dfs(root); vector<int> vec(n); for (int i = 0; i < n; i++) vec[i] = i; sort(vec.begin(), vec.end(), [&] (int u, int v) { return dfn[u] < dfn[v]; }); memset(dp, -1, sizeof(dp)); dp[0][0] = 0; for (auto u : vec) { for (int i = 0; i < m; i++) if (~dp[dfn[u]][i]) { dp[r[u]][i + 1] = max(dp[r[u]][i + 1], dp[dfn[u]][i] + x[u]); } for (int i = 0; i <= m; i++) { dp[dfn[u] + 1][i] = max(dp[dfn[u] + 1][i], dp[dfn[u]][i]); } } printf("%d\n", dp[n][m]); return 0; }

Compilation message (stderr)

biochips.cpp: In function 'int main()':
biochips.cpp:24: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:30:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &b);
                         ^
#Verdict Execution timeMemoryGrader output
Fetching results...