QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#107384 | #33. Cat in a tree | snpmrnhlol | 0 | 2ms | 3812kb | C++20 | 1.9kb | 2023-05-21 05:16:45 | 2023-05-21 05:16:49 |
Judging History
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%