QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#431593#33. Cat in a treeNevll0 2ms9108kbC++14960b2024-06-05 19:34:212024-06-05 19:34:22

Judging History

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

  • [2024-06-05 19:34:22]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:9108kb
  • [2024-06-05 19:34:21]
  • 提交

answer

# include <bits/stdc++.h>
# define ll long long
# define fi first
# define se second
# define pii pair<int, int>
using namespace std;

vector<int> edge[200001];
int dpt[200001];

int main() {
	int N, D;
	scanf("%d %d", &N, &D);
	
	vector< pii > arr(N);
	arr[0] = {0, 0};
	for(int i=1;i<N;i++) {
		int x;
		scanf("%d", &x);
		edge[i].push_back(x);
		edge[x].push_back(i);
		
		arr[i].fi = arr[x].fi - 1;
		arr[i].se=  i;
	}
	sort(arr.begin(), arr.end());
	
	for(int i=0;i<N;i++) dpt[i] = -1e9;
	
	int ans = 0;
	for(int i=0;i<N;i++) {
		if(dpt[arr[i].se] == -1e9) {
			ans++;
			
			queue<int> bfs;
			dpt[arr[i].se] = 0;
			bfs.push(arr[i].se);
			
			while(bfs.size()) {
				int x = bfs.front();
				bfs.pop();
				
				if(dpt[x] == D - 1) continue;
				
				for(auto p : edge[x]) {
					if(dpt[p] == -1e9) {
						dpt[p] = dpt[x] + 1;
						bfs.push(p);
					}
				}
			}
		}
	}
	
	printf("%d\n", ans);
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

input:

10 2
0
0
2
2
0
3
4
7
2

output:

6

result:

ok single line: '6'

Test #2:

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

input:

10 3
0
0
2
1
4
4
3
1
7

output:

4

result:

ok single line: '4'

Test #3:

score: 11
Accepted
time: 0ms
memory: 8396kb

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
Wrong Answer
time: 2ms
memory: 9108kb

input:

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

output:

4

result:

wrong answer 1st lines differ - expected: '3', found: '4'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%