oj.uz

Submission #339113

# Submission time Handle Problem Language Result Execution time Memory
339113 2020-12-24T15:53:35 Z fixikmila Biochips (IZhO12_biochips) C++14
0 / 100
 2000 ms 153704 KB 
#include <bits/stdc++.h>
#ifndef LOCAL_RUN
    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC optimize("fast-math")
    #pragma GCC target("avx2,tune=native")
#endif
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;
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;
}

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 39 ms 22892 KB Output is correct
5 Correct 68 ms 25068 KB Output is correct
6 Correct 78 ms 25068 KB Output is correct
7 Execution timed out 2085 ms 153704 KB Time limit exceeded
8 Halted 0 ms 0 KB -