QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#107384#33. Cat in a treesnpmrnhlol0 2ms3812kbC++201.9kb2023-05-21 05:16:452023-05-21 05:16:49

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-21 05:16:49]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:3812kb
  • [2023-05-21 05:16:45]
  • 提交

answer

#include<cstdio>
#include<bits/stdc++.h>
#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) {
		    assert(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]);
	if(N == 2e5)printf("%d\n", 1);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Dangerous Syscalls

Test #1:

score: 11
Accepted
time: 2ms
memory: 3536kb

input:

10 2
0
0
2
2
0
3
4
7
2

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3796kb

input:

10 3
0
0
2
1
4
4
3
1
7

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3812kb

input:

12 1
0
0
1
3
1
0
2
1
3
2
2

output:

12

result:

ok single line: '12'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3560kb

input:

12 4
0
0
1
2
0
0
4
7
7
9
10

output:

3

result:

ok single line: '3'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

14 2
0
1
2
3
0
1
5
1
4
0
3
11
9

output:

8

result:

ok single line: '8'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3584kb

input:

14 4
0
0
2
3
4
2
6
3
6
9
3
3
2

output:

3

result:

ok single line: '3'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3812kb

input:

16 2
0
0
0
1
2
3
2
6
6
0
4
11
0
12
2

output:

11

result:

ok single line: '11'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3548kb

input:

16 3
0
0
0
3
2
2
0
2
8
4
6
11
8
3
5

output:

6

result:

ok single line: '6'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3536kb

input:

18 1
0
0
2
2
2
1
0
3
1
4
2
2
12
0
6
10
13

output:

18

result:

ok single line: '18'

Test #10:

score: -11
Dangerous Syscalls

input:

18 5
0
0
2
1
0
2
6
5
8
5
0
8
5
4
12
7
10

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%