oj.uz

Submission #843226

# Submission time Handle Problem Language Result Execution time Memory
843226 2023-09-03T19:39:15 Z dungz Biochips (IZhO12_biochips) C++17
100 / 100
 206 ms 403476 KB 
//dau tuyen
//dau tuyen
//dau tuyen
#pragma GCC optimize ("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define task "task"
#define task "task"
#define prll pair<ll,ll>
#define pb push_back
#define ld long double
const ll MIN=-1e18,MAX=1e18,MOD=1e9+7;
vector<int> a[200005];
int in[200005],out[200005];
int d=0;
int f[200005][505];
int val[200005];
void dfs(int u,int par)
{
    in[++d]=u;
    for(auto i:a[u])
    {
        if(i!=par)
        {
            dfs(i,u);
        }
    }
    out[u]=d;
}
int main(){
//    #ifndef ONLINE_JUDGE
//           freopen (task".inp", "r", stdin);
//           freopen (task".out", "w", stdout);
//    #endif
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        a[x].push_back(i);
//        cout<<x<<" "<<i<<endl;
        val[i]=y;

    }
    dfs(0,-1);
    for(int i=1;i<=d+1;i++) for(int j=1;j<=m;j++) f[i][j]=-2e9;
//    for(int i=1;i<=d;i++) cout<<in[i]<<" ";
//    cout<<endl;
    for(int i=d;i>=2;i--)
    {
        for(int j=1;j<=m;j++)
        {
            f[i][j]=max(val[in[i]]+f[out[in[i]]+1][j-1],f[i+1][j]);
//            ans=max(ans,f[i][j]);
        }
    }
    cout<<f[2][m];
}
/*
o(n*m^2) done

*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 6 ms 25176 KB Output is correct
5 Correct 6 ms 27224 KB Output is correct
6 Correct 7 ms 27224 KB Output is correct
7 Correct 126 ms 302924 KB Output is correct
8 Correct 128 ms 302976 KB Output is correct
9 Correct 181 ms 366196 KB Output is correct
10 Correct 206 ms 403476 KB Output is correct