oj.uz

Submission #41122

# Submission time Handle Problem Language Result Execution time Memory
41122 2018-02-13T02:45:15 Z wzy Biochips (IZhO12_biochips) C++14
0 / 100
 2000 ms 414424 KB 
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <utility>
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 = 0 , maxrv = 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;
	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 == ed[rv[maxrv]] + 1 && j < m) return -eps;
	if(dp[i][j] != -1) return dp[i][j];
	if(j == m) return 0;
	if(i > maxrv) 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);
	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(st[root] , 0);
	printf("%d\n" , qq);
}

Compilation message

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

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 400320 KB Output is correct
2 Correct 287 ms 400556 KB Output is correct
3 Correct 290 ms 400556 KB Output is correct
4 Correct 303 ms 401412 KB Output is correct
5 Correct 315 ms 401584 KB Output is correct
6 Correct 321 ms 401584 KB Output is correct
7 Execution timed out 2059 ms 414424 KB Time limit exceeded
8 Halted 0 ms 0 KB -