| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 41124 |
2018-02-13T03:10:23 Z |
wzy |
Biochips (IZhO12_biochips) |
C++11 |
|
284 ms |
400376 KB |
#include <bits/stdc++.h>
using namespace std;
#define eps (int) 1e9
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define pb push_back
int root , rv[200005], t = -1 , maxrv = 0 , dp[200005][505] , c[200005] , n , m , st[200005] , ed[200005];
vector<int> adj[200005];
bool vis[200005][505];
void dfs(int x , int y){
st[x] = ++t;
rv[st[x]] = x;
maxrv = max(maxrv , st[x]);
for(int i = 0 ; i < adj[x].size() ; i++){
int v = adj[x][i];
if(v == y) continue;
dfs(v,x);
}
ed[x] = t;
return;
}
int solve(int i , int j){
if(i == n-1 && j == m - 1){
return dp[i][j] = c[i];
}
else if(i >= n-1) return -eps;
if(vis[i][j]) return dp[i][j];
vis[i][j] = true;
return dp[i][j] = max(solve(i +1 , j), solve(ed[rv[i]] + 1 , j + 1) + c[rv[i]]);
}
int32_t main(){
scanf("%d%d" , &n , &m);
memset(dp, -1 , sizeof dp);
for(int i = 0 ; i <n; i++){
int x , y;
scanf("%d%d" , &x, &y);
c[i] = y;
if(x == 0){
root = i;
continue;
}
else{
adj[i].pb(x-1);
adj[x-1].pb(i);
}
}
dfs(root, root);
int qq = solve(0 , 0);
printf("%d\n" , qq);
}
Compilation message
biochips.cpp: In function 'void dfs(int, int)':
biochips.cpp:14:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < adj[x].size() ; i++){
^
biochips.cpp: In function 'int32_t main()':
biochips.cpp:34:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d" , &n , &m);
^
biochips.cpp:38:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d" , &x, &y);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
284 ms |
400376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
