# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
306098 | shivensinha4 | Biochips (IZhO12_biochips) | C++17 | 446 ms | 22136 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'
int n, m;
const int MXN = 2e5, MXM = 500;
vi adj[MXN+1], dp[MXN+1];
int val[MXN+1], lf[MXN+1];
void dfs(int p, int parent) {
lf[p] = !adj[p].size();
for (int i: adj[p]) if (i != parent) {
dfs(i, p);
lf[p] += lf[i];
}
lf[p] = min(lf[p], m);
dp[p].resize(lf[p]+1);
for (int i: adj[p]) {
vi curr = dp[p];
for_(j, 0, lf[p]+1) if (j == 0 or dp[p][j] != 0) for_(k, 1, min(lf[i]+1, lf[p]-j+1)) if (dp[i][k] != 0) {
curr[j+k] = max(curr[j+k], dp[p][j] + dp[i][k]);
}
swap(curr, dp[p]);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |