Submission #124793

#	Time	Username	Problem	Language	Result	Execution time	Memory
124793		model_code	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	97 ms	19960 KiB

catinatree

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int N,D;
vector<vector<int> > T;
vector<int> opt, optdist, sacrdist;

void DFS(int pos) {
	// Base case: pos is a leaf
	if(T[pos].size() == 0) {
		opt[pos] = 1;
		optdist[pos] = 0;
		sacrdist[pos] = D;
		return;
	}
	
	int v = T[pos][0];
	DFS(v);
	if(optdist[v] + 1 >= D) {
		opt[pos] = opt[v] + 1;
		optdist[pos] = 0;
		sacrdist[pos] = optdist[v] + 1;
	} else {
		opt[pos] = opt[v];
		optdist[pos] = optdist[v] + 1;
		sacrdist[pos] = sacrdist[v] + 1;
	}
	
	for(int i = 1; i < T[pos].size(); ++i) {
		int v = T[pos][i];
		DFS(v);
		
		// distance between closest points and 
		// distance to root
		// in the 4 possible solution combinations. 
		int doo = optdist[pos] + optdist[v] + 1;
		int mdoo = min(optdist[pos], optdist[v] + 1);
		
		int dos = optdist[pos] + sacrdist[v] + 1;
		int mdos = min(optdist[pos], sacrdist[v] + 1);

		int dso = sacrdist[pos] + optdist[v] + 1;
		int mdso = min(sacrdist[pos], optdist[v] + 1);

		int dss = sacrdist[pos] + sacrdist[v] + 1;
		int mdss = min(sacrdist[pos], sacrdist[v] + 1);
		
		if(doo >= D) {
			opt[pos] += opt[v];
			optdist[pos] = mdoo;
			sacrdist[pos] = max(mdos, mdso);
		} else if (dos >= D || dso >= D) {
			opt[pos] += opt[v] - 1;
			if(dos >= D) optdist[pos] = mdos; else optdist[pos] = 0;
			if(dso >= D) optdist[pos] = max(optdist[pos], mdso);
			sacrdist[pos] = mdss;
		} else {
			cout << "error!" << endl;
			exit(0);
		}
	}
}

int main() {
	scanf("%d%d", &N, &D);
	T = vector<vector<int> > (N);
	opt = vector<int> (N, 0);
	optdist = vector<int> (N, 0);
	sacrdist = vector<int> (N, 0);
	for(int i = 1; i < N; ++i) {
		int a;
		scanf("%d", &a);
		T[a].push_back(i);
	}
	DFS(0);
	printf("%d\n", opt[0]);
	return 0;
}

Compilation message (stderr)

catinatree.cpp: In function 'void DFS(int)':
catinatree.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < T[pos].size(); ++i) {
                 ~~^~~~~~~~~~~~~~~
catinatree.cpp:49:7: warning: unused variable 'dss' [-Wunused-variable]
   int dss = sacrdist[pos] + sacrdist[v] + 1;
       ^~~
catinatree.cpp: In function 'int main()':
catinatree.cpp:69: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:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~

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