oj.uz

Submission #143007

# Submission time Handle Problem Language Result Execution time Memory
143007 2019-08-12T14:54:08 Z davitmarg Cat in a tree (BOI17_catinatree) C++17
0 / 100
 8 ms 5240 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

int n,d,dp[1502][1502],upd[1502][1502],sz[200005],ans;
vector<int> g[200005];
void dfs(int v)
{
	sz[v]=1;
	for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i];
		dfs(to);
	}

	dp[v][0]=1;
	for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i];
		for(int k=0;k<=d;k++)
		{
			upd[v][min(k+1,d-k-1)]=max(upd[v][min(k+1,d-k-1)],dp[to][k]+dp[v][d-1-k]);
			upd[v][k+1]=max(dp[to][k],upd[v][k+1]);
		}

		sz[v]+=sz[to];
		for(int k=d;k>=0;k--)
		{
			dp[v][k]=max(dp[v][k],upd[v][k]);
			dp[v][k]=max(dp[v][k],dp[v][k+1]);
			upd[v][k]=0;
		}
	}

	// cout<<"! "<<v<<endl;
	// for(int k=0;k<=d && k<=sz[v];k++)
	// 	cout<<k<<" = "<<dp[v][k]<<"\n";

	for(int k=0;k<=d && k<=sz[v];k++)
		ans=max(ans,dp[v][k]);
}
int main()
{
	cin>>n>>d;
	for(int i=1;i<n;i++)
	{
		int p;
		scanf("%d",&p);
		g[p].PB(i);
	}
	dfs(0);
	cout<<ans<<endl;
	return 0;
}
 
/*
 

 
*/

Compilation message

catinatree.cpp: In function 'void dfs(int)':
catinatree.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
catinatree.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
catinatree.cpp: In function 'int main()':
catinatree.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&p);
   ~~~~~^~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 8 ms 5112 KB Output is correct
4 Correct 8 ms 5112 KB Output is correct
5 Correct 8 ms 5084 KB Output is correct
6 Correct 7 ms 5112 KB Output is correct
7 Correct 7 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 8 ms 5112 KB Output is correct
11 Correct 8 ms 5112 KB Output is correct
12 Correct 6 ms 5112 KB Output is correct
13 Correct 6 ms 5112 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 6 ms 5112 KB Output is correct
16 Correct 7 ms 5112 KB Output is correct
17 Correct 6 ms 5112 KB Output is correct
18 Incorrect 6 ms 5112 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 8 ms 5112 KB Output is correct
4 Correct 8 ms 5112 KB Output is correct
5 Correct 8 ms 5084 KB Output is correct
6 Correct 7 ms 5112 KB Output is correct
7 Correct 7 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 8 ms 5112 KB Output is correct
11 Correct 8 ms 5112 KB Output is correct
12 Correct 6 ms 5112 KB Output is correct
13 Correct 6 ms 5112 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 6 ms 5112 KB Output is correct
16 Correct 7 ms 5112 KB Output is correct
17 Correct 6 ms 5112 KB Output is correct
18 Incorrect 6 ms 5112 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5240 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 8 ms 5112 KB Output is correct
4 Correct 8 ms 5112 KB Output is correct
5 Correct 8 ms 5084 KB Output is correct
6 Correct 7 ms 5112 KB Output is correct
7 Correct 7 ms 5112 KB Output is correct
8 Correct 6 ms 5112 KB Output is correct
9 Correct 6 ms 5112 KB Output is correct
10 Correct 8 ms 5112 KB Output is correct
11 Correct 8 ms 5112 KB Output is correct
12 Correct 6 ms 5112 KB Output is correct
13 Correct 6 ms 5112 KB Output is correct
14 Correct 6 ms 5112 KB Output is correct
15 Correct 6 ms 5112 KB Output is correct
16 Correct 7 ms 5112 KB Output is correct
17 Correct 6 ms 5112 KB Output is correct
18 Incorrect 6 ms 5112 KB Output isn't correct
19 Halted 0 ms 0 KB -