oj.uz

Submission #519402

# Submission time Handle Problem Language Result Execution time Memory
519402 2022-01-26T10:12:45 Z tphuc2908 Biochips (IZhO12_biochips) C++14
100 / 100
 592 ms 408700 KB 
#include<bits/stdc++.h>

using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define repi(i,x,y) for(int i = x; i >= y; --i)
#define ci(x) int x; cin>> x
#define TC(t) ci(t); while(t--)
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define cii(x, y) ci(x); ci(y)
#define ciii(x, y, z) ci(x); ci(y); ci(z)
#define mp make_pair
//#define int long long
typedef long long ll;
typedef vector<int> vi;
const int N = 2e5 + 5;
const int NN = 16 + 15;
const int mod = 1e9 + 7;
const int mod1 = 1e9 + 9;
const int pi = 31;
const int inf = 1e9 + 6;
const int block = 500;
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};

void readfile(){
    #ifdef ONLINE_JUDGE
    #else
        freopen("text.inp", "r", stdin);
    #endif // ONLINE_JUDGE
//    freopen("biochip.inp", "r", stdin);
//    freopen("biochip.out", "w", stdout);
}

int n, m;
vector<int> g[N];
int val[N];

void inp(){
    cin >> n >> m;
    rep(i,1,n){
        cii(cha, v);
        g[i].pb(cha);
        g[cha].pb(i);
        val[i] = v;
    }
}

int sz[N], dp[505], f[N][505];

void dfs(int s, int p){
    sz[s] = 1;
    for(int v : g[s])
        if(v!=p){
            dfs(v, s);
            sz[s] += sz[v];
        }
    fill(dp + 0, dp + m + 1, 0);
    int cnt = 0;
    for(int v : g[s]){
        if(v==p) continue;
        rep(i,0,cnt)
            rep(j,0,min(sz[v], m)){
                if(i + j > m) break;
                dp[i + j] = max(dp[i+j], f[s][i] + f[v][j]);
            }
        rep(i,0,min(cnt+sz[v], m))
            f[s][i] = dp[i], dp[i] = 0;
        cnt = min(cnt + sz[v], m);
    }
    f[s][1] = max(f[s][1], val[s]);
}

void process(){
    dfs(0, -1);
    cout << f[0][m];
}

int main() {
  //  readfile();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    while(cin >> n >> m){
        inp();
        process();
//        reset();
//    }
    return 0;
}

Compilation message

biochips.cpp: In function 'void readfile()':
biochips.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         freopen("text.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4996 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 3 ms 5148 KB Output is correct
4 Correct 18 ms 22988 KB Output is correct
5 Correct 19 ms 25244 KB Output is correct
6 Correct 19 ms 25284 KB Output is correct
7 Correct 327 ms 304752 KB Output is correct
8 Correct 307 ms 304684 KB Output is correct
9 Correct 458 ms 370304 KB Output is correct
10 Correct 592 ms 408700 KB Output is correct