Submission #41119

#TimeUsernameProblemLanguageResultExecution timeMemory
41119wzyBiochips (IZhO12_biochips)C++14
0 / 100
2048 ms417708 KiB
#include <stdio.h> #include <stdint.h> #include <string.h> #include <vector> #include <algorithm> #include <iostream> #include <utility> using namespace std; #define eps (int) 1e9 #define pb push_back int root , rv[200005], t = 0 , dp[200005][505] , c[200005] , n , m , st[200005] , ed[200005]; vector<int> adj[200005]; void dfs(int x , int y){ st[x] = ++t; rv[st[x]] = 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(dp[i][j] != -1) return dp[i][j]; if(j > m) return -eps; if(j == m) return 0; if(i > t) return - eps; dp[i][j] = 0; 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); for(int i = 0 ; i < 200005 ; i++){ c[i] = -eps; rv[i] = eps; ed[i] = eps; for(int j = 0 ; j < 505 ; j++) dp[i][j] = -1; } 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(st[root] , 0); printf("%d\n" , qq); }

Compilation message (stderr)

biochips.cpp: In function 'void dfs(int, int)':
biochips.cpp:17: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:36: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:45: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 timeMemoryGrader output
Fetching results...