oj.uz

Submission #1114154

# Submission time Handle Problem Language Result Execution time Memory
1114154 2024-11-18T08:56:08 Z 0pt1mus23 Biochips (IZhO12_biochips) C++14
0 / 100
 337 ms 406600 KB 
// el psy congroo
#include <bits/stdc++.h>
using namespace std;
#define int int
#define ins insert      
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 2e5 +1, inf = LLONG_MAX, LG = 20;
vector<int> graph[sze];
int val[sze];
int k;
int dp[sze][501];
int mx[sze];
int a,b;
void dfs(int node,int par=-1){
    a= 0,b;
    for(auto v:graph[node]){
        if(v!=par){
            dfs(v,node);
            b = mx[v];
            a=min(a,k);
            b=min(b,k);
            for(int i = a;i>=0;i--){
                if( (!i) ||  dp[node][i]){
                    for(int j=  0;j<=b && ( (i+j)<=k);j++){
                        if(!(j) || dp[v][j]){
                            dp[node][i+j]=max(dp[node][i+j],dp[node][i] + dp[v][j]);
                        }
                    }
                }
            }
            a+=b;
            mx[node]=max(mx[node],a);
        }
    }
    dp[node][1]=max(dp[node][1],val[node]);
    mx[node]=max(mx[node],(int)1);
}

void fast(){
    int n,p,w;
    cin>>n>>k;
    int root =0;
    for(int i=1;i<=n;i++){
        p,w;
        cin>>p>>w;
        root|=(!p) * i;
        if(p!=0){
            graph[p].pb(i);
            graph[i].pb(p);
        }
        val[i]=w;
    }
    dfs(root);
    cout<<dp[root][k]<<endl;
}
 
signed main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);
 
    int tt = 1;
    // cin>>tt;
 
    while(tt--){
        fast();
    }
 
    return 0;
}

Compilation message

biochips.cpp:11:45: warning: overflow in conversion from 'long long int' to 'int' changes value from '9223372036854775807' to '-1' [-Woverflow]
   11 | const int mod = 1e9 +7, sze = 2e5 +1, inf = LLONG_MAX, LG = 20;
      |                                             ^~~~~~~~~
biochips.cpp: In function 'void dfs(int, int)':
biochips.cpp:19:11: warning: right operand of comma operator has no effect [-Wunused-value]
   19 |     a= 0,b;
      |           ^
biochips.cpp: In function 'void fast()':
biochips.cpp:48:9: warning: left operand of comma operator has no effect [-Wunused-value]
   48 |         p,w;
      |         ^
biochips.cpp:48:12: warning: right operand of comma operator has no effect [-Wunused-value]
   48 |         p,w;
      |            ^

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6736 KB Output isn't correct
2 Incorrect 2 ms 6736 KB Output isn't correct
3 Incorrect 2 ms 6736 KB Output isn't correct
4 Incorrect 20 ms 24400 KB Output isn't correct
5 Incorrect 21 ms 26696 KB Output isn't correct
6 Incorrect 21 ms 26704 KB Output isn't correct
7 Incorrect 262 ms 303432 KB Output isn't correct
8 Incorrect 263 ms 303440 KB Output isn't correct
9 Incorrect 305 ms 368456 KB Output isn't correct
10 Incorrect 337 ms 406600 KB Output isn't correct