oj.uz

Submission #41115

# Submission time Handle Problem Language Result Execution time Memory
41115 2018-02-13T00:31:09 Z wzy Biochips (IZhO12_biochips) C++14
0 / 100
 316 ms 419320 KB 
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pii pair<int,int>
#define ieps (int) 1e6
#define eps (int) 1e9
#define mp make_pair
#define pb push_back
vector<int> adj[ieps];
int dp[200005][505] ,n , m;
int label[ieps] , root;
int rvst[ieps];
int st[ieps] , ed[ieps] , t = 0;
void dfs(int x , int y){
	rvst[t] = x;
	st[x] = t++;
	for(int i = 0 ; i < adj[x].size() ; i++){
		int v = adj[x][i];
		if(v == y) continue;
		dfs(v,x);
	}
	ed[x] = t;
}


int solve(int i , int j){
	if(dp[i][j] != -1) return dp[i][j];
	dp[i][j] = 0;
	if(i > t) return -eps;
	if(i == t && j == m){
		return 0;
	}
	if(i == t) return -eps;
	return dp[i][j] = max(solve(i + 1 , j) , solve(ed[rvst[i]] + 1 , j + 1) + label[rvst[i]]);
}
int32_t main(){
	scanf("%d%d" , &n , &m);
	for(int i = 0 ; i < n; i++){
		int y , x;
		scanf("%d%d" , &y , &x);
		label[i] = x;
		if(y==0){
			root = i;
			continue;
		}
		else{
			y--;
			adj[i].pb(y);
			adj[y].pb(i);
		}
	}
	memset(dp , -1 , sizeof dp);
	dfs(root, root);
	printf("%d\n" , solve(0 , 0));
}

Compilation message

biochips.cpp: In function 'void dfs(int, int)':
biochips.cpp:18: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:38: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:41:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d" , &y , &x);
                          ^

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 316 ms 419320 KB Output isn't correct
2 Halted 0 ms 0 KB -