oj.uz

Submission #701639

# Submission time Handle Problem Language Result Execution time Memory
701639 2023-02-21T16:10:58 Z hgmhc Biochips (IZhO12_biochips) C++17
90 / 100
 488 ms 24680 KB 
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define fi first
#define se second
#define dbg(...) fprintf(stderr,__VA_ARGS__)

const int N = 2e5+3, M = 503;
int n, m, a[N], p[N], r;
int sub[N];
vector<int> child[N];
vector<ll> dp[N];
// tree optimization. O(NM).
// dfs order의 차이가 m 이하로 나도록 부분 배열 선택하는 꼴.

void pre(int s = r, int e = 0) {
    sub[s] = 1;
    for (auto u : child[s]) if (u != e) {
        pre(u,s), sub[s] += sub[u];
    }
}
void solve(int s = r, int e = 0) {
    dp[s].resize(min(m,sub[s])+1);
    for (auto u : child[s]) if (u != e) {
        solve(u,s);
        per(x,1,min(m,sub[s])) rep(y,0,min(x,sub[u])) {
            Mup(dp[s][x],dp[u][y]+dp[s][x-y]);
        }
    }
    Mup(dp[s][1],ll(a[s]));
}

int main() {
    scanf("%d %d", &n, &m);
    rep(i,1,n) {
        scanf("%d %d", &p[i], &a[i]);
        if (p[i] == 0) r = i;
        else child[p[i]].push_back(i);
    }
    pre();
    solve();
    printf("%lld", dp[r][m]);
}

Compilation message

biochips.cpp: In function 'int main()':
biochips.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
biochips.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%d %d", &p[i], &a[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
90.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Incorrect 5 ms 9684 KB Output isn't correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 9 ms 10548 KB Output is correct
5 Correct 10 ms 10484 KB Output is correct
6 Correct 11 ms 10480 KB Output is correct
7 Correct 231 ms 19548 KB Output is correct
8 Correct 235 ms 19588 KB Output is correct
9 Correct 338 ms 22904 KB Output is correct
10 Correct 488 ms 24680 KB Output is correct