Submission #1206882

#TimeUsernameProblemLanguageResultExecution timeMemory
1206882mohyayBiochips (IZhO12_biochips)C++20
60 / 100
2102 ms475892 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> #define endl '\n' using ll = int; #define pb push_back #define pF first #define pS second #define SP <<' '<< const ll mod = 998244353; ll dp[212345][600], a[212345], sz[212345]; vector<ll> v[212345]; ll m; void dfs(ll i, ll p) { dp[i][0] = 0; for (auto j : v[i]) { if (j != p) dfs(j, i); for (int k = min(sz[i],m); k >= 0; k--) { for (int k1 = 0; k1 <= k; k1++) { dp[i][k] = max(dp[i][k], dp[i][k1] + dp[j][abs(k-k1)]); } } } dp[i][1] = max(dp[i][1], a[i]); } void dfssz(ll i, ll p) { sz[i] = 1; for (auto j : v[i]) { if (j != p) dfssz(j, i); sz[i] += sz[j]; } } int main() { ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); ll n; cin>>n>>m; for (int i=1; i<=n; i++) for (int j = 0; j<=m; j++) dp[i][j] = -INT_MAX; ll root; for (int i=1; i<=n; i++) { ll p, x; cin>>p>>x; v[p].pb(i); a[i] = x; if (p == 0) root = i; } dfssz(root, 0); dfs(root, 0); cout << dp[root][m]; }
#Verdict Execution timeMemoryGrader output
Fetching results...