oj.uz

답안 #524476

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
524476 2022-02-09T09:10:28 Z Pety 바이오칩 (IZhO12_biochips) C++14
100 / 100
 316 ms 400152 KB 
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int INF = 1e9;
const int MOD = 1e9 + 7;

int n, m, dp[200002][502], v[200002], sz[200002];
vector<int>G[200002];

void dfs (int nod) {
  dp[nod][1] = 0;
  sz[nod] = 1;
  for (auto it : G[nod]) {
    dfs(it);
    for (int i = min(m, sz[nod]); i >= 0; i--)
      for (int j = 1; j <= min(m, sz[it]); j++)
        if (i + j <= m)
          dp[nod][i + j] = max(dp[nod][i] + dp[it][j], dp[nod][i + j]);
        else
          break;
    sz[nod] += sz[it];
  }
  dp[nod][1] = max(dp[nod][1], v[nod]);
}

int main () 
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n >> m;
  int root;
  for (int i = 1; i <= n;i++) {
    int x, y;
    cin >>  x>> y;
    v[i] = y;
    if (x != 0)
      G[x].push_back(i);
    else
      root = i;
  }
  dfs(root);
  cout << dp[root][m];
  
  
  
  return 0;
}

Compilation message

biochips.cpp: In function 'int main()':
biochips.cpp:44:21: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |   cout << dp[root][m];
      |                     ^

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5196 KB Output is correct
4 Correct 14 ms 22604 KB Output is correct
5 Correct 15 ms 24824 KB Output is correct
6 Correct 15 ms 24780 KB Output is correct
7 Correct 210 ms 297076 KB Output is correct
8 Correct 207 ms 298520 KB Output is correct
9 Correct 270 ms 362500 KB Output is correct
10 Correct 316 ms 400152 KB Output is correct