Submission #1207007

#TimeUsernameProblemLanguageResultExecution timeMemory
1207007HishamAlshehriBiochips (IZhO12_biochips)C++20
70 / 100
735 ms402384 KiB
#include <bits/stdc++.h> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> using namespace std; // using namespace __gnu_pbds; // #define int long long #define mod 1000000007 #define base 7001 #define base2 757 #define F first #define S second // #define pi acos(-1) #define double long double // #define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> // #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> // #pragma GCC optimize("O3,Ofast,unroll-loops") // #pragma GCC target("avx2,sse3,sse4,avx") mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); constexpr int maxn = 300001; const int N = 1 << (int)(ceil(log2(maxn))); int n, m, a[maxn], siz[maxn]; vector<int> dp[maxn], adj[maxn]; int sizfind(int v) { siz[v] = 1; for (int u : adj[v]) siz[v] += sizfind(u); return siz[v]; } void dfs(int v) { vector<int> ret; ret.resize(m + 5, -1e8); ret[0] = 0; for (int u : adj[v]) { dfs(u); } int cur = 0; if (adj[v].size()) { cur = siz[adj[v][0]]; ret = dp[adj[v][0]]; } for (int i = 1; i < adj[v].size(); i++) { int u = adj[v][i]; for (int j = 0; j <= min(siz[u], m); j++) { for (int k = 0; k + j <= m && k <= min(cur, m); k++) { dp[v][j + k] = max(dp[v][j + k], ret[k] + dp[u][j]); } } ret = dp[v]; cur += siz[u]; } for (int i = 0; i <= min(siz[v], m); i++) dp[v][i] = max(dp[v][i], ret[i]); // dp[v] = ret; // if (v==7) for (int i : dp[v]) cout << i << " "; return; } signed main() { cin.tie(0) -> sync_with_stdio(0); cin >> n >> m; int rt = 0; for (int i = 1; i <= n; i++) { int p, x; cin >> p >> x; a[i] = x; if (!p) {rt = i; continue;} adj[p].push_back(i); } for (int i = 1; i <= n; i++) dp[i].resize(m + 5, -1e8); for (int i = 1; i <= n; i++) dp[i][0] = 0, dp[i][1] = a[i]; sizfind(rt); dfs(rt); // for (int i = 1; i <= n; i++) { // for (int j = 0; j <= m; j++) cout << dp[i][j] << ' '; // cout << "\n"; // } // for (int i = 1; i <= n; i++) cout << siz[i] << " "; cout << dp[rt][m]; }
#Verdict Execution timeMemoryGrader output
Fetching results...