oj.uz

Submission #124795

# Submission time Handle Problem Language Result Execution time Memory
124795 2019-07-04T02:05:48 Z model_code Cat in a tree (BOI17_catinatree) C++17
11 / 100
 3 ms 504 KB 
#include<cassert>
#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);
    assert(N <= 18);
	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

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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 252 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 252 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 252 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 252 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 252 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 252 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 252 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 252 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 252 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -