oj.uz

Submission #106695

# Submission time Handle Problem Language Result Execution time Memory
106695 2019-04-19T17:34:25 Z Pajaraja Biochips (IZhO12_biochips) C++17
100 / 100
 388 ms 11572 KB 
#include <bits/stdc++.h>
#define MAXN 200007
using namespace std;
vector<int> g[MAXN];
int w[MAXN],dp[MAXN],dpp[MAXN],nz[MAXN],dk[MAXN],t,wn[MAXN];
void dfs(int s)
{
	int in=t;
	for(int i=0;i<g[s].size();i++) dfs(g[s][i]);
	dk[++t]=in; wn[t]=w[s];
}
int main()
{
	int n,m,rt;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		int p; scanf("%d%d",&p,&w[i]);
		if(p==0) rt=i;
		else g[p].push_back(i);
	}
	dfs(rt); dp[0]=-1000000000; dpp[0]=-1000000000;
	for(int i=1;i<=n;i++) dpp[i]=max(wn[i],dpp[i-1]);
	for(int k=1;k<m;k++)
	{
		for(int i=1;i<=n;i++) dp[i]=max(dpp[dk[i]]+wn[i],dp[i-1]);
		for(int i=1;i<=n;i++) dpp[i]=dp[i];
	}
	printf("%d",dpp[n]);
}

Compilation message

biochips.cpp: In function 'void dfs(int)':
biochips.cpp:9:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) dfs(g[s][i]);
              ~^~~~~~~~~~~~
biochips.cpp: In function 'int main()':
biochips.cpp:15: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:18:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int p; scanf("%d%d",&p,&w[i]);
          ~~~~~^~~~~~~~~~~~~~~~~
biochips.cpp:22:5: warning: 'rt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs(rt); dp[0]=-1000000000; dpp[0]=-1000000000;
  ~~~^~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 5 ms 5120 KB Output is correct
3 Correct 5 ms 4992 KB Output is correct
4 Correct 12 ms 5412 KB Output is correct
5 Correct 14 ms 5504 KB Output is correct
6 Correct 13 ms 5376 KB Output is correct
7 Correct 195 ms 10488 KB Output is correct
8 Correct 203 ms 10616 KB Output is correct
9 Correct 299 ms 11128 KB Output is correct
10 Correct 388 ms 11572 KB Output is correct