oj.uz

Submission #81146

# Submission time Handle Problem Language Result Execution time Memory
81146 2018-10-24T02:35:31 Z wzy Biochips (IZhO12_biochips) C++11
100 / 100
 642 ms 415200 KB 
#include <bits/stdc++.h>
using namespace std;
#define time tr
#define pb push_back
int c[200005], r[200005], outfx[200005] , dp[200005][505];
vector<int> adj[200005];
int n , m , time = 0;
int root = -1;
int in[200005] , out[200005];
void solve(int x , int y){
	in[x] = ++time;
	r[in[x]] = c[x];
	dp[in[x]][1] = c[x];
	for(auto p : adj[x]){
		if(p == y) continue;
		solve(p, x);
	}
	out[in[x]] = time;
}

int32_t main(){
	scanf("%d%d" ,&n , &m);
	for(int i = 1 ; i <= n; i ++){
		int x , y;
		scanf("%d%d" , &x , &y);
		c[i] = y;
		if(x == 0) root = i;
		else{
			adj[x].pb(i);
			adj[i].pb(x);
		}
	}
	solve(root, root);
	int ans = 0;
	for(int i = time ; i >= 1 ; i--){
		for(int j = 1 ; j  <= m ; j++){
			if(i+1 <= time) dp[i][j] = max(dp[i][j], dp[i+1][j]);
			if(out[i] + 1 <= time){
			dp[i][j] = max(dp[i][j] , dp[out[i] + 1][j-1] + r[i]);
			}
			if(j == m) ans = max(ans , dp[i][j]);
		}
	}
	printf("%d\n" , ans);
}

Compilation message

biochips.cpp: In function 'int32_t main()':
biochips.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d" ,&n , &m);
  ~~~~~^~~~~~~~~~~~~~~~~
biochips.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d" , &x , &y);
   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5244 KB Output is correct
3 Correct 7 ms 5396 KB Output is correct
4 Correct 26 ms 23248 KB Output is correct
5 Correct 27 ms 25552 KB Output is correct
6 Correct 29 ms 25788 KB Output is correct
7 Correct 432 ms 306520 KB Output is correct
8 Correct 425 ms 307996 KB Output is correct
9 Correct 557 ms 375256 KB Output is correct
10 Correct 642 ms 415200 KB Output is correct