#include <bits/stdc++.h>
#define z exit(0)
using namespace std;
const int N = 2e5 + 5, inf = 2e8;
vector<int> g[N];
int x[N], tin[N], tout[N], timer = 0, V[N], dp[N][501];
void dfs(int u, int p){
tin[u] = timer++;
for(int v: g[u]) dfs(v, u);
tout[u] = timer++;
}
int bit[501][N];
void upd(int k, int i, int val){ for(++i; i<N; i+=i&-i) bit[k][i] = max(bit[k][i], val);}
int qry(int k, int i){ int res = -inf; for(++i; i; i-=i&-i) res = max(res, bit[k][i]); return res;}
bool cmp(int i, int j){ return tout[i] < tout[j]; }
signed main(){
int n, m, r = 0; scanf("%d %d", &n, &m);
for(int v = 0, u; v<n; ++v){
scanf("%d %d", &u, x+v); --u;
if(u != -1) g[u].push_back(v);
else r = v;
V[v] = v;
fill(dp[v], dp[v]+m+1, -inf);
}
for(int k = 0; k<=m; ++k) fill(bit[k], bit[k]+m+1, -inf);
dfs(r, r);
sort(V, V+n, cmp);
upd(0, 0, dp[0][0] = 0);
upd(1, 0, dp[0][1] = x[V[0]]);
int ans = -inf;
for(int i = 1; i<n; ++i){
int low = 0, high = i-1, idx = -1;
while(low <= high){
int mid = low + ((high-low)>>1);
if(tout[V[mid]] < tin[V[i]]) low = mid+1, idx = mid;
else high = mid-1;
}
for(int k = 0; k<=m; ++k){
dp[i][k] = max(dp[i][k], dp[i-1][k]);
if(idx != -1) dp[i][k] = max(dp[i][k], qry(k-1, idx) + x[V[i]]);
}
for(int k = 0; k<=m; ++k) upd(k, i, dp[i][k]);
ans = max(ans, dp[i][m]);
}
printf("%d", ans);
}
Compilation message
biochips.cpp: In function 'int main()':
biochips.cpp:17:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | int n, m, r = 0; scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
biochips.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | scanf("%d %d", &u, x+v); --u;
| ~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14680 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
12648 KB |
Output isn't correct |
| 3 |
Incorrect |
4 ms |
24920 KB |
Output isn't correct |
| 4 |
Incorrect |
24 ms |
42480 KB |
Output isn't correct |
| 5 |
Incorrect |
30 ms |
43348 KB |
Output isn't correct |
| 6 |
Incorrect |
41 ms |
45140 KB |
Output isn't correct |
| 7 |
Execution timed out |
2072 ms |
459092 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2076 ms |
449796 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2080 ms |
486740 KB |
Time limit exceeded |
| 10 |
Runtime error |
1981 ms |
524288 KB |
Execution killed with signal 9 |
