Submission #135697

#	Time	Username	Problem	Language	Result	Execution time	Memory
135697		khsoo01	Cat in a tree (BOI17_catinatree)	C++11	100 / 100	591 ms	173944 KiB

catinatree

#include<bits/stdc++.h>
using namespace std;
const int N = 200005, B = 300;
int n, d, ans;
vector<int> dt[N], adj[N], tmp;

void sol1 (int C) {
	dt[C].push_back(d);
	int S = 1;
	for(auto &T : adj[C]) {
		sol1(T);
		int M = 0; tmp.clear();
		for(int i=0;i<dt[T].size();i++) {
			int D1 = dt[T][i] + 1;
			if(D1 >= d) M = max(M, i);
			for(int j=0;j<dt[C].size();j++) {
				int D2 = dt[C][j];
				if(D1 + D2 >= d) {
					int V = min(D1, D2);
					if(tmp.size() <= i+j) tmp.push_back(V);
					else tmp[i+j] = max(tmp[i+j], min(D1, D2));
				}
			}
		}
		for(int i=0;i<tmp.size();i++) {
			if(dt[C].size() <= i) dt[C].push_back(tmp[i]);
			else dt[C][i] = max(dt[C][i], tmp[i]);
		}
		S += M;
	}
	for(int i=dt[C].size();--i;) {
		dt[C][i-1] = max(dt[C][i-1], dt[C][i]);
	}
	if(dt[C].size() <= S) dt[C].push_back(0);
}

void sol2 (int C) {
	dt[C].resize(d);
	int S = 0;
	for(auto &T : adj[C]) {sol2(T); S += dt[T][d-1];}
	dt[C][0] = S + 1;
	for(int k=1;k<d;k++) {
		int M = 0;
		if(k >= d-k) {
			for(auto &T : adj[C]) dt[C][k] += dt[T][k-1];
		}
		else {
			for(auto &T : adj[C]) {
				dt[C][k] += dt[T][d-k-1];
				M = max(M, dt[T][k-1]-dt[T][d-k-1]);
			}
			dt[C][k] += M;
		}
	}
	for(int k=d;--k;) dt[C][k-1] = max(dt[C][k-1], dt[C][k]);
}

int main()
{
	scanf("%d%d",&n,&d);
	for(int i=1;i<n;i++) {
		int T; scanf("%d",&T);
		adj[T].push_back(i);
	}
	if(d > B) {sol1(0); ans = (int)dt[0].size()-1;}
	else {sol2(0); ans = dt[0][0];}
	printf("%d\n",ans);
}

Compilation message (stderr)

catinatree.cpp: In function 'void sol1(int)':
catinatree.cpp:13:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<dt[T].size();i++) {
               ~^~~~~~~~~~~~~
catinatree.cpp:16:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<dt[C].size();j++) {
                ~^~~~~~~~~~~~~
catinatree.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(tmp.size() <= i+j) tmp.push_back(V);
         ~~~~~~~~~~~^~~~~~
catinatree.cpp:25:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<tmp.size();i++) {
               ~^~~~~~~~~~~
catinatree.cpp:26:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(dt[C].size() <= i) dt[C].push_back(tmp[i]);
       ~~~~~~~~~~~~~^~~~
catinatree.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(dt[C].size() <= S) dt[C].push_back(0);
     ~~~~~~~~~~~~~^~~~
catinatree.cpp: In function 'int main()':
catinatree.cpp:60:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&d);
  ~~~~~^~~~~~~~~~~~~~
catinatree.cpp:62:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int T; scanf("%d",&T);
          ~~~~~^~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 49 / 49