Submission #236921

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
236921	2020-06-03T20:29:12 Z	mohamedsobhi777	Biochips (IZhO12_biochips)	C++14	0 / 100	771 ms	524288 KB

biochips

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 7;

int n, k;
int root;
int dp[N][505];
int ans[N];
int a[N];
vector<int> adj[N];

void dfs(int x)
{

        int ret = 0;
        dp[x][0] = 0;
        for (auto u : adj[x])
        {
                dfs(u);
                for (int j = 0; j <= k; j++)
                {
                        for (int k1 = 0; k1 <= k; k1++)
                        {
                                dp[x][j] = max(dp[x][j], dp[u][k1] + dp[x][k - k1]);
                        }
                }
        }
        for (int i = k; i; i--)
        {
                dp[x][i] = max(dp[x][i], dp[x][i - 1] + a[x]);
        }
        ans[x] = max(dp[x][n], dp[x][n - 1] + a[x]);
}

int t, st[N], en[N], ver[2*N];
int sz[N];

int dfz(int x)
{
        sz[x] = 1;
        st[x] = ++t;
        ver[t] = x;
        for (auto u : adj[x])
        {
                sz[x] += dfz(u);
        }
        en[x] = ++t;
        return sz[x];
}

int solve(int x, int r)
{

        if (r > k)
                return -1e9;
        if (x > 2 * n)
        {
                if (r == k)
                        return 0;
                return -1e9;
        }
        if (dp[x][r] != -1)
                return dp[x][r];
        int ret = 0;
        ret = max(ret, solve(x + 1, r));
        ret = max(ret, solve(x + sz[ver[x]] * 2 , r + 1) + a[ver[x]]);
        return dp[x][r] = ret;
}

int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        //freopen("in.in", "r", stdin);
        cin >> n >> k;
        for (int i = 1; i <= n; i++)
        {
                int u, c;
                cin >> u >> a[i];
                if (u)
                        adj[u].push_back(i);
                else
                        root = i;
        }
        memset(dp, -1, sizeof dp);
        dfz(root);
        cout << solve(1, 0);
        return 0;
}

Compilation message

biochips.cpp: In function 'void dfs(int)':
biochips.cpp:17:13: warning: unused variable 'ret' [-Wunused-variable]
         int ret = 0;
             ^~~
biochips.cpp: In function 'int main()':
biochips.cpp:80:24: warning: unused variable 'c' [-Wunused-variable]
                 int u, c;
                        ^

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	211 ms	400376 KB	Output is correct
2	Correct	204 ms	400376 KB	Output is correct
3	Correct	207 ms	400376 KB	Output is correct
4	Correct	219 ms	401656 KB	Output is correct
5	Correct	245 ms	401784 KB	Output is correct
6	Correct	228 ms	401784 KB	Output is correct
7	Runtime error	771 ms	524288 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Halted	0 ms	0 KB	-