Submission #913985

#TimeUsernameProblemLanguageResultExecution timeMemory
913985daoquanglinh2007Biochips (IZhO12_biochips)C++17
100 / 100
258 ms405240 KiB
#include <bits/stdc++.h> using namespace std; const int NM = 2e5, MM = 500, inf = 1e9+7; int N, M, p[NM+5], x[NM+5], timer = 0, tin[NM+5], tout[NM+5], tour[NM+5]; vector <int> son[NM+5]; int dp[NM+5][MM+5]; void dfs_euler_tour(int u){ tin[u] = ++timer; tour[timer] = u; for (int v : son[u]){ dfs_euler_tour(v); } tout[u] = timer; } int main(){ // freopen("BIOCHIPS.inp", "r", stdin); // freopen("BIOCHIPS.out", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> M; for (int i = 1; i <= N; i++){ cin >> p[i] >> x[i]; son[p[i]].push_back(i); } dfs_euler_tour(0); for (int i = 1; i <= M; i++) dp[timer+1][i] = -inf; for (int i = timer; i >= 1; i--){ int u = tour[i]; for (int j = 1; j <= M; j++){ dp[i][j] = -inf; if (dp[tout[u]+1][j-1] != -inf) dp[i][j] = max(dp[i][j], dp[tout[u]+1][j-1]+x[u]); if (dp[i+1][j] != -inf) dp[i][j] = max(dp[i][j], dp[i+1][j]); } } cout << dp[1][M]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...