# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
672216 | 2022-12-15T05:20:45 Z | Alihan_8 | Biochips (IZhO12_biochips) | C++17 | 404 ms | 524288 KB |
#include <bits/stdc++.h> // include <ext/pb_ds/assoc_container.hpp> // include <ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; using namespace std; #define all(x) x.begin(), x.end() #define pb push_back // define ordered_set tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> #define mpr make_pair #define ln '\n' void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);} #define int long long const int N = 2e5+1, M = 501; vector <int> g[N]; int val[N], dp[N][M], m; void chmax(int &l, int r){l = max(l, r);}; void dfs(int n){ vector <int> _list; dp[n][1] = val[n]; for ( auto to: g[n] ){ dfs(to); for ( int i = 1; i <= m; i++ ){ if ( _list.empty() ) continue; chmax(dp[to][i], dp[_list.back()][i-1]+val[to]); } _list.pb(to); } if ( !_list.empty() ){ for ( int i = 1; i <= m; i++ ){ chmax(dp[n][i], dp[_list.back()][i]); } } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n >> m; int root = -1; for ( int i = 1; i <= n; i++ ){ int x; cin >> x >> val[i]; if ( !x ){ root = i; continue; } g[x].pb(i); } dfs(root); cout << dp[root][m]; cout << '\n'; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 4948 KB | Output isn't correct |
2 | Correct | 3 ms | 4948 KB | Output is correct |
3 | Incorrect | 3 ms | 5332 KB | Output isn't correct |
4 | Incorrect | 22 ms | 40148 KB | Output isn't correct |
5 | Incorrect | 25 ms | 44460 KB | Output isn't correct |
6 | Incorrect | 24 ms | 44448 KB | Output isn't correct |
7 | Runtime error | 330 ms | 524288 KB | Execution killed with signal 9 |
8 | Runtime error | 404 ms | 524288 KB | Execution killed with signal 9 |
9 | Runtime error | 301 ms | 524288 KB | Execution killed with signal 9 |
10 | Runtime error | 335 ms | 524288 KB | Execution killed with signal 9 |