QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#431593 | #33. Cat in a tree | Nevll | 0 | 2ms | 9108kb | C++14 | 960b | 2024-06-05 19:34:21 | 2024-06-05 19:34:22 |
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%