제출 #1207062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1207062		ibsha	Biochips (IZhO12_biochips)	C++20	100 / 100	587 ms	402476 KiB

biochips

//#include <bits/stdc++.h>
#include <random>
#include "set"
#include <iostream>
#include "vector"
#include "deque"
#include "climits"
#include "algorithm"
#include "stack"
#include "map"
#include "unordered_set"
#include "bitset"
#include "queue"


/*
            ====================================================================================================
            #*###*############*####*#####*####*############*#########################################*##########
            %%%%%%%%%###%##*##=*+++=+++++++++++++*@#@%%###%%%%%%%%%%%%%%%%%%%%@%@@@%@@@@@@@@@@@@@%%%%%%%@@@%%%%#
            %%%%%%%%%%#####*##=*++++++++++++++++=*@%@%%###%%%%%%%%%%%%%%%%%%%%%%%%%%@@@%%@@@@@@@@%%%@@%%@@@%%%%#
            %%%%%%%%%######*##=*+++++++++++++++++*@%@%%###%%%%%%%%%%%%%%%%%%%%%%%%%%@@%%@@@@@@@@@%%#%%%%@@%#%#%#
            %%%%%%%%%%%####*##=*++++++++++++++++=+@%@%%###%@@@%%%%%%%%%%%%%%%%%%%%%%%@@%%%%@@@@@%%@%%%%%@%%%####
            %%%%%%%%%%####%*##=*++++++++++++++++=+@%@%%###%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@%@@@%%%%%@%######
            %%%%%%%%%%####%*##=*++++++++++++++===+@%@%%###%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%@@@@%#@%%%%%%@%#######
            %%%%%%%%%%#####*##+++++++++++=++++=+++@%#%##%#######%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@#%%%%%%@########
            %%%%%%%%%%#####*##+*+++++++++++++++==@%%%%%@##:-%=-=-+@%%%%%%%%%%%%%%%%%%%%%%%@@%%%@@@%%%%%@%%######
            %%%%%%%%%%#####*##+*++++++++++++=+*%%%%%%%%#%*.@:-%+-++%%%%%%%%%%%%%%%%%%%@%%%@%%%%%%%%%%%@@%#######
            %%%%%%%%%%####%*##=*=++++++++++++@%%%%%%%%%%%%#@@@@@@@=-@%%%%%%%%%%%%%%%%%%%%%@@%%%%%%%%%%@@@#######
            %%%%%%%%%%####%*##+*++++++++++++%@%%@%%%%%%%%#%@###*#%%@@%%%%%%%%%%%%%%%%%%%%%@@%%%%%%%%%%@@@%%%####
            %%%%%%%%%%####%*##+*+++++++++==@@%@@@@%%@%###%#@#=%@@@@@@@#=+@%%%%%%%%%%%%%%%%@@%%%%%%%%%%@@@%%%####
            %%%%%%%%%%####%*##*++++++++++++@@@@@@%#%%%%@#@@@@@@@@@@@@@@@@@-#%%%%%%%%%%%%%%@%%%%%%%%%%@@@%%%#####
            %%%%%%%%%#########=*++++++++++@@@@@%#@@@%%@@@@@@@@@@@@@@@@@@@@%@%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%#####
            %%%%%%%%######%*##=*++++++++++@%%@@@@@@@@@%%%####%@@%%%%@@@@@@@%#%%%%%%%%%%%%%@@%%%%%%%%%%%%%%%#####
            %%%%%%%%##########=*++++++***#%%@@@@@@%%##*++++++***#*++*#%@@@@%%%%%%%%%%%%%%%@@%%%%%%%%%%%%%%%%####
            %%%%%%%%######%###=*++++++#@%%@%@@@@%#*+++++====++++++++++*#@@@@%%%%%%%%%%%%%%@@%%%%%%%%%%%%%%%%%###
            %%%%%%%%######%###=*++++*%%%%@@@@@@@#+++++++=========++++++*#@@@@@%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%####
            %%%%%%%%%#####%###=*++**%@#@@@@@@@@%+++=================++++*@@@@%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%##
            %%%%%%%%%#########=*+*#*@%@@@@@@%@%*++*+**##*++======*####*#*%@@@@%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%#
            %%%%%%%%%%########=#+*@%@@@@@@%@@@#*+=-=****#*+=+++=**#**#*+*#%@@%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%###
            %%%%%%%%%%########+#*#@@@@%%%@@@%%#*+++*+=##+#*+*++##*+%**#**#%@@@@@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%##
            %%%%%%%%%%########=#**@@@@@@@@@@@@#*+=+=+++++++*==+*#*****++*#%%@@@%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%#
            %%%%%%%%%#########=#**@@@@@@@@@@@@#*+===++++==+=+++**++=++++#%@@@@@%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%##
            %%%%%%%%%#####%###=##%@@@@@@@@@@@@#**+========++====++==+++*#%@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%##
            %%%%%%%#%#########+#+%@%#@@@@@@@@@%**+========+++===*++++++#%@@@%@%%%%%%%%@%%%%@%%%%%%%%%%%%%%%%####
            %%%%%%%%%%%#######=#+@@@@@@@@@@@@@#**++===+++****#**##*+++*%%@@@@@@%%%%@@@@@@@@@@@%%%%%%%%%%%%%%####
            @%%%%%##%%########+***@@@@@@@@@@@%#***++++*****#%###%%****#%@@@@%@%%%%%%%%%%%%%%%%%%%%%%%%#%%%%%%@@@
            %%%%%%%#%##%%%%###+**##%#@@@@@@@###***+++++++++++++*******#@@@@@@%%#%%%%%%%%%%%@%%%%%%%%%%%%%%%%%##%
            #@##%%##%##%######+**+++*@%##%%%%*********+++++++**********@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%##%
            %@##%#%%%####%####+#*+*+++++++++#%**************************#%#*#%%%%%%#%%%%%%%%%%%%%%%%%%%%%%%#%%%#
            @%%###%#%########*++===========++#@*++******##########******#++======@%%%%%%%%@%%%%%%%%%%%%%%%%%#%%#
            %%%##%##%##%###*++=========+=++++++*#********######*******+*=+==--=====*%%%#%%@%%%%%%%%%%%%%%%@%%%%#
            %%%##%%#%#####+++++*+=========+==+++**#******#####*******+*+++++==:======*%#%%@%%%%%%%%%%%%%%%%%%%#%
            %%%##%%%%#++==========--=----====+++++*##*****###*****+++#*===--+=====-------+**#@@%%%%%%%%%%%%%%%%%
            %#%%%+*++==========-=--=---------========++*@********+=%#===========----------======+@%%%%%%%%%%%%%%
            %#%***++========----------------------======++@.+++++*+==========---------------=-=====@%%%%%%%%%%%%
            %%**+++=========------------=---------=======+++*+*+%++========------------------==-====%%%%%%%%%%%%
            %**++++=========--===-=--=======------===========#*++============---------====----======+*%%%%%%%%%%
            #**+++++====+============+++++========-===========+*==============--=====+++++=====+===+=+*%%%%%%%%%
            #****+++==++++=====++++++****+++++===--=========+++++++=================+++***+++++++++++++%%%%%%%%%
            #*****+++++++++++++++++***##***++===-=---=======++*=*++++==============++++**#***+++++++++*+%%%%%%%%
            #******++++***++++++***######*+=====-----=--====++*+**+++======-=--=======+*#*##***+*+****#+@@%%%%%%
            ##********+**********####%%%+++++=====-----=====++*+***+++================++*#%####*********%@%+%%%%
            ###***************######%%#**++++++=============++++*#*+++======-========++++*%%####******#*%@@%%%%%
            ####****************##%%@#***++++++++++=========+++*=**++==============++++++**%%###*********#%%*%%%
            *****************+====*%%*********+++++===+====+++++++**++==+=*=====+++++++****@##++++=+****++*@%%%%
            *************+++=====--=@************+++++++++++++++******+++++++++++++++******#*+=====+++++*+++@%%%
            ***+++++*++++++=========+########**#%%*******++******%##***+++*++++++++++*******++++====++=++++**%%%
            ***+++========++========+%######*%###%#**************%###***************########***++++++++++++**#%%
            ***+++++++=====+++====+++*@#####%%%%%%######********#######**********###%%%%##%#**#*+++++==+++++**%%
            ***++++++++=======++++++**@%#######################%*#%%%#################%%#%%##**#*+++++++++++***%
            ***+++++**+++==========+*+#%%#######################**#%%###################%@%###*##*++++*+++++***%
            ****+**+++++++=======++*#*#@%%%%%%%%###########%%%#*****##%#%###########%%%%@%%%######+++++++++++***
            #*****+++++++++=====+++***#%%%%%%%%%%%%%%%%%%%%%%**++===+*#%%%%%%%%%%%%%%%%%@@%%#######*++++===+++**
            #*****+++++++=======+++**#%%%%%%%##############*+++==-===++*####%%%%%%##%%%%@@%%%######**+=====+++**
            ##****+++++++=====+*++***#%%%%%%%###########***++++++++++=++**############%%%%%%%%####****#*+=++++**
            ====================================================================================================
*/



using namespace std;
using ll = int;
using ull = unsigned long long;
//#define MOD 1000000007
#define endl '\n'
#define pb(v,i) (v).push_back(i)
#define vll vector<ll>
#define pll pair<ll,ll>
#define _ << ' ' <<
#define clearvis for (int i=0; i<maxn;visited[i++]=false)

const ll maxn = 3e5+2, maxm = 502;

ll dp[maxn][maxm+2];
ll val[maxn];

vll edges[maxn];
bool visited[maxn];
ll sz[maxn];
void dfs(ll node){
    for (ll nd : edges[node]) dfs(nd);

    for (ll nd: edges[node]) {
        for (ll k=min(maxm, sz[node]); k>=1; k--){
            for (ll j=min(k, sz[nd]); j >= 0; j--) {
                dp[node][k] = max(dp[node][k], dp[node][k - j] + dp[nd][j]);
            }
        }
    }
    dp[node][1] = max(dp[node][1], val[node]);
}

void dsz(ll node){
    sz[node] = 1;
    for (ll nd : edges[node]){
        dsz(nd);
        sz[node] += sz[nd];
    }
}


void solve() {
    // cout << fixed << setprecision(6);

    ll n,m; cin >> n >> m;
    ll root;
    for (int i=1;i<=n;i++){
        ll p,x; cin >> p >> x;
        if (p == 0) root = i;
        else{
            pb(edges[p],i);
        }
        val[i] = x;
    }
    dsz(root);
    dfs(root);

    cout << dp[root][m];
}


signed main() {
    //ios::sync_with_stdio(false);cin.tie(nullptr);
    //freopen("walk.in","r",stdin);
    //freopen("walk.out","w",stdout);
    ll t=1;
    //cin >> t;
    for (int i=1; i<=t; i++){
    //    cout << "Case " << i << ":\n";
        solve();
        cout << endl;
    }


    return 0;
}

• Subtask 1: 100 / 100