oj.uz

답안 #236923

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
236923 2020-06-03T20:36:45 Z mohamedsobhi777 바이오칩 (IZhO12_biochips) C++14
0 / 100
 72 ms 81272 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e4 + 7;

int n, k;
int root;
int dp[N*2][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

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 79864 KB Output is correct
2 Correct 49 ms 79872 KB Output is correct
3 Correct 52 ms 79868 KB Output is correct
4 Correct 65 ms 81144 KB Output is correct
5 Correct 67 ms 81272 KB Output is correct
6 Correct 72 ms 81144 KB Output is correct
7 Runtime error 13 ms 3712 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -