oj.uz

Submission #339094

# Submission time Handle Problem Language Result Execution time Memory
339094 2020-12-24T15:21:38 Z fixikmila Biochips (IZhO12_biochips) C++14
0 / 100
 2000 ms 149356 KB 
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll>pll;
typedef long double ld;
ll bin_pow(ll a,ll b){
    if(b==0)return 1;
    if(b%2==0){
        ll t=bin_pow(a,b/2);
        return t*t%MOD;
    }
    else return a*bin_pow(a,b-1)%MOD;
}
vector<ll>graph[200000];
int dp[200000][501],a[200000];
bool used[200000];
int t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
void dfs(ll v,ll p=-1){
    used[v]=true;
    if(graph[v].size()==1){
            dp[v][1]=a[v];
            return;
    }

    for(auto u : graph[v]){
        if(used[u])continue;
        dfs(u,v);
    }
        for(auto u : graph[v]){
            if(u==p)continue;
            vector<ll>c(m+1);
            for(int j=0;j<=m;j++){

                    for(int i=j;i<=m;i++){
                            //if(v==2&&u==4&&i==2)cout<<j<<" "<<dp[4][1]<<dp[2]<<"ss"<<endl;
                        c[i]=max(ll(dp[v][i-j]+dp[u][j]),c[i]);
                    }

            }
            for(int z=m;z>=0;z--){
                dp[v][z]=c[z];
            }
        }
        dp[v][1]=a[v];
    for(auto u : graph[v]){
        if(u==p)continue;
        dp[v][1]=max(dp[v][1],dp[u][1]);
    }
}
int main()
{
    //freopen("stones.in","r",stdin);
    //freopen("stones.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s;
    cin>>n>>m;
    for(int i=0;i<n;i++){
            cin>>x>>y;
            x--;
            a[i]=y;
            if(x==-1){
                z=i;
                continue;
            }
        graph[i].push_back(x);
        graph[x].push_back(i);
    }
    dfs(z);
    ans=dp[z][m];
    //cout<<dp[2][2]<<endl;
    cout<<ans;
    return 0;
}

Compilation message

biochips.cpp:18:52: warning: overflow in conversion from 'long long int' to 'int' changes value from '9223372036854775807' to '-1' [-Woverflow]
   18 | int t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                                    ^~~~~~~~~
biochips.cpp:18:65: warning: overflow in conversion from 'long long int' to 'int' changes value from '-9223372036854775808' to '0' [-Woverflow]
   18 | int t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                                                 ^~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5228 KB Output is correct
4 Correct 41 ms 22892 KB Output is correct
5 Correct 57 ms 25196 KB Output is correct
6 Correct 83 ms 25196 KB Output is correct
7 Execution timed out 2103 ms 149356 KB Time limit exceeded
8 Halted 0 ms 0 KB -