Submission #1259259

#TimeUsernameProblemLanguageResultExecution timeMemory
1259259SDAdzs1tgBiochips (IZhO12_biochips)C++20
100 / 100
374 ms406480 KiB
#include<bits/stdc++.h> using namespace std; const int maxn = 2e5 + 10; vector<int> adj[maxn]; int n, m, in[maxn], out[maxn], cnt = 0; int a[maxn]; vector<int> x; void dfs(int u, int p) { in[u] = ++cnt; x.push_back(u); for(auto v : adj[u]) { if(v == p) continue; dfs(v, u); } out[u] = cnt; } int dp[maxn][510]; signed main () { cin >> n >> m; int root = 0; for(int i = 1; i <= n; i++) { int v, c; cin >> v >> c; if(v == 0) { root = i; continue; } adj[v].push_back(i); a[i] = c; } x.push_back(0); dfs(root, -1); for(int i = 0; i <= n + 1; i++) { for(int j = 1; j <= m; j++) dp[i][j] = -1e18; } for(int i = x.size() - 1; i >= 0; i--) { int t = x[i]; for(int j = 1; j <= m; j++) { dp[i][j] = max(dp[i][j], dp[i + 1][j]); dp[i][j] = max(dp[i][j], dp[out[t] + 1][j - 1] + a[t]); } } cout << dp[1][m]; }

Compilation message (stderr)

biochips.cpp: In function 'int main()':
biochips.cpp:33:56: warning: overflow in conversion from 'double' to 'int' changes value from '-1.0e+18' to '-2147483648' [-Woverflow]
   33 |                 for(int j = 1; j <= m; j++) dp[i][j] = -1e18;
      |                                                        ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...