oj.uz

Submission #717442

# Submission time Handle Problem Language Result Execution time Memory
717442 2023-04-01T23:32:53 Z Ahmed57 Biochips (IZhO12_biochips) C++14
0 / 100
 282 ms 524288 KB 
#include <bits/stdc++.h>

using namespace std;
int en[200001];
vector<int> adj[200001];
long long cost[200001];
int n,m;int timer = 0;
vector<int> euler;
void dfs(int i,int pr){
    ++timer;
    euler.push_back(i);
    for(auto j:adj[i]){
        if(j==pr)continue;
        dfs(j,i);
    }
    en[i] = timer;
}
long long dp[200001][501];
long long solve(int i,int rem){
    if(i==n)return (rem==0?0:-1e18);
    if(dp[i][rem]!=-1)return dp[i][rem];
    long long c1 = solve(i+1,rem);
    if(rem)c1 = max(c1,solve(en[euler[i]],rem-1)+cost[euler[i]]);
    return dp[i][rem] = c1;
}
signed main(){
    //ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    int ro = 0;
    for(int i = 0;i<n;i++){
        int a,b;
        cin>>a>>b;
        cost[i+1] = b;
        if(a==0)ro = i+1;
        else{
        adj[a].push_back(i+1);
        adj[i+1].push_back(a);
        }
    }
    dfs(ro,0);
    memset(dp,-1,sizeof dp);
    cout<<solve(0,m)<<"\n";
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 186 ms 524288 KB Execution killed with signal 9
2 Runtime error 186 ms 524288 KB Execution killed with signal 9
3 Runtime error 217 ms 524288 KB Execution killed with signal 9
4 Runtime error 195 ms 524288 KB Execution killed with signal 9
5 Runtime error 201 ms 524288 KB Execution killed with signal 9
6 Runtime error 189 ms 524288 KB Execution killed with signal 9
7 Runtime error 259 ms 524288 KB Execution killed with signal 9
8 Runtime error 282 ms 524288 KB Execution killed with signal 9
9 Runtime error 261 ms 524288 KB Execution killed with signal 9
10 Runtime error 275 ms 524288 KB Execution killed with signal 9