#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#define endl "\n"
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
template<class T> inline void fix(T &x) {if(x >= mod | x <= -mod) {x %= mod;} if(x < 0) {x += mod;}}
#define out(x) cout << __LINE__ << ": " << (#x) << " = " << (x) << endl
const ll MAX_N = 1e5 + 10;
const ll MAX_W = 510;
vector<ll> g[MAX_N];
ll in[MAX_N], out[MAX_N], arr[MAX_N];
ll tme = -1;
ll dp[MAX_N][MAX_W];
void dfs(ll x) {
in[x] = tme; tme ++;
for(auto it : g[x]) {
dfs(it);
}
out[x] = tme;
}
bool cmp(ll a, ll b) {
return in[a] < in[b];
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
ll n, w;
cin >> n >> w;
vector<ll> ord;
for(ll i = 1; i <= n; i ++) {
ll p;
cin >> p >> arr[i];
g[p].push_back(i);
ord.push_back(i);
}
dfs(0);
sort(ord.begin(), ord.end(), cmp);
for(ll i = 0; i < MAX_N; i ++) {fill_n(dp[i], MAX_W, -mod);}
dp[0][0] = 0;
for(ll i = 0; i < ord.size(); i ++) {
for(ll j = 0; j < MAX_W; j ++) {
chkmax(dp[i + 1][j], dp[i][j]);
chkmax(dp[out[ord[i]]][j + 1], dp[i][j] + arr[ord[i]]);
}
}
cout << dp[ord.size()][w] << endl;
return 0;
}
Compilation message
biochips.cpp: In function 'int main()':
biochips.cpp:49:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(ll i = 0; i < ord.size(); i ++) {
| ~~^~~~~~~~~~~~
biochips.cpp:9:78: warning: iteration 509 invokes undefined behavior [-Waggressive-loop-optimizations]
9 | template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
| ~~^~~
biochips.cpp:50:25: note: within this loop
50 | for(ll j = 0; j < MAX_W; j ++) {
| ~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
228 ms |
401912 KB |
Output is correct |
| 2 |
Correct |
220 ms |
401912 KB |
Output is correct |
| 3 |
Correct |
233 ms |
401916 KB |
Output is correct |
| 4 |
Incorrect |
258 ms |
402572 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
