#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define lb lower_bound
#define ins insert
#define sz(x) (int)(x).size()
const int MOD = 1e9+7;
void ckmin(int& a, int b){
a = min(a, b);
}
const int mx = 200005;
int N, D;
vi adj[mx];
int closest_dist[mx];
int getDist(int a, int b){
return 0;
}
bool done[mx];
int sub[mx];
void genSub(int node, int p = -1){
sub[node] = 1;
for(auto u: adj[node]){
if(done[u]) continue;
if(u == p) continue;
genSub(u, node);
sub[node]+=sub[u];
}
}
int getCen(int node){
genSub(node);
int cur = node;
int p = -1;
for(auto u: adj[cur]){
if(done[u]) continue;
if(u == p) continue;
if(sub[u]*2 > sub[node]){
p = cur;
cur = u;
}
else{
break;
}
}
return cur;
}
int centroid_par[mx][20];
int centroid_dist[mx][20];
vpi queries[mx];
int dist[mx];
void genDist(int node, int d = 0, int p = -1){
dist[node] = d;
for(auto u: adj[node]){
if(done[u]) continue;
if(u == p) continue;
genDist(u, d+1, node);
}
}
void genCenPar(int node, int c_par = -1){
int cen = getCen(node);
// cout << "node, cen, c_par: " << node << ", " << cen << ", " << c_par << "\n";
centroid_par[cen][0] = cen;
centroid_par[cen][1] = c_par;
for(int i = 2; i < 20; i++){
if(c_par == -1){
centroid_par[cen][i] = -1;
}
else{
centroid_par[cen][i] = centroid_par[c_par][i-1];
}
}
for(int i = 0; i < 20; i++){
int CEN = centroid_par[cen][i];
queries[CEN].pb(mp(cen, i));
}
done[cen] = 1;
for(auto u: adj[cen]){
if(!done[u]){
genCenPar(u, cen);
}
}
done[cen] = 0;
genDist(cen);
for(auto u: queries[cen]){
centroid_dist[u.f][u.s] = dist[u.f];
}
}
int root_dist[mx];
void genRootDist(int node, int d = 0, int p = -1){
root_dist[node] = d;
for(auto u: adj[node]){
if(u == p) continue;
genRootDist(u, d+1, node);
}
}
int getMinDist(int node){
int res = MOD;
for(int i = 0; i < 20; i++){
int cen = centroid_par[node][i];
if(cen != -1){
ckmin(res, closest_dist[cen]+centroid_dist[node][i]);
}
}
return res;
}
void updateClosest(int node){
for(int i = 0; i < 20; i++){
int cen = centroid_par[node][i];
ckmin(closest_dist[cen], centroid_dist[node][i]);
}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> N >> D;
for(int i = 1; i < N; i++){
int xi;
cin >> xi;
adj[xi].pb(i);
adj[i].pb(xi);
}
genCenPar(0);
for(int i = 0; i < N; i++){
closest_dist[i] = MOD;
}
genRootDist(0, 0);
vpi order;
for(int i = 0; i < N; i++){
order.pb(mp(root_dist[i], i));
}
sort(order.rbegin(), order.rend());
// for(int i = 0; i < N; i++){
// for(int j = 0; j < 20; j++){
// cout << "cen_par: " << i << " " << j << " " << centroid_par[i][j] << "\n";
// }
// for(int j = 0; j < 20; j++){
// cout << "cen_dist: " << i << " " << j << " " << centroid_dist[i][j] << "\n";
// }
// }
int ans = 0;
for(auto u: order){
int node = u.s;
int min_dist = getMinDist(node);
if(min_dist >= D){
updateClosest(node);
ans++;
}
}
cout << ans << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
9676 KB |
Output is correct |
2 |
Correct |
7 ms |
9676 KB |
Output is correct |
3 |
Correct |
7 ms |
9676 KB |
Output is correct |
4 |
Correct |
7 ms |
9704 KB |
Output is correct |
5 |
Correct |
7 ms |
9676 KB |
Output is correct |
6 |
Correct |
7 ms |
9676 KB |
Output is correct |
7 |
Correct |
7 ms |
9676 KB |
Output is correct |
8 |
Correct |
7 ms |
9676 KB |
Output is correct |
9 |
Correct |
8 ms |
9744 KB |
Output is correct |
10 |
Correct |
7 ms |
9716 KB |
Output is correct |
11 |
Correct |
6 ms |
9676 KB |
Output is correct |
12 |
Correct |
6 ms |
9712 KB |
Output is correct |
13 |
Correct |
6 ms |
9676 KB |
Output is correct |
14 |
Correct |
6 ms |
9676 KB |
Output is correct |
15 |
Correct |
7 ms |
9712 KB |
Output is correct |
16 |
Correct |
7 ms |
9720 KB |
Output is correct |
17 |
Correct |
6 ms |
9676 KB |
Output is correct |
18 |
Correct |
7 ms |
9756 KB |
Output is correct |
19 |
Correct |
7 ms |
9680 KB |
Output is correct |
20 |
Correct |
6 ms |
9676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
9676 KB |
Output is correct |
2 |
Correct |
7 ms |
9676 KB |
Output is correct |
3 |
Correct |
7 ms |
9676 KB |
Output is correct |
4 |
Correct |
7 ms |
9704 KB |
Output is correct |
5 |
Correct |
7 ms |
9676 KB |
Output is correct |
6 |
Correct |
7 ms |
9676 KB |
Output is correct |
7 |
Correct |
7 ms |
9676 KB |
Output is correct |
8 |
Correct |
7 ms |
9676 KB |
Output is correct |
9 |
Correct |
8 ms |
9744 KB |
Output is correct |
10 |
Correct |
7 ms |
9716 KB |
Output is correct |
11 |
Correct |
6 ms |
9676 KB |
Output is correct |
12 |
Correct |
6 ms |
9712 KB |
Output is correct |
13 |
Correct |
6 ms |
9676 KB |
Output is correct |
14 |
Correct |
6 ms |
9676 KB |
Output is correct |
15 |
Correct |
7 ms |
9712 KB |
Output is correct |
16 |
Correct |
7 ms |
9720 KB |
Output is correct |
17 |
Correct |
6 ms |
9676 KB |
Output is correct |
18 |
Correct |
7 ms |
9756 KB |
Output is correct |
19 |
Correct |
7 ms |
9680 KB |
Output is correct |
20 |
Correct |
6 ms |
9676 KB |
Output is correct |
21 |
Incorrect |
18 ms |
10612 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
9676 KB |
Output is correct |
2 |
Correct |
7 ms |
9676 KB |
Output is correct |
3 |
Correct |
7 ms |
9676 KB |
Output is correct |
4 |
Correct |
7 ms |
9704 KB |
Output is correct |
5 |
Correct |
7 ms |
9676 KB |
Output is correct |
6 |
Correct |
7 ms |
9676 KB |
Output is correct |
7 |
Correct |
7 ms |
9676 KB |
Output is correct |
8 |
Correct |
7 ms |
9676 KB |
Output is correct |
9 |
Correct |
8 ms |
9744 KB |
Output is correct |
10 |
Correct |
7 ms |
9716 KB |
Output is correct |
11 |
Correct |
6 ms |
9676 KB |
Output is correct |
12 |
Correct |
6 ms |
9712 KB |
Output is correct |
13 |
Correct |
6 ms |
9676 KB |
Output is correct |
14 |
Correct |
6 ms |
9676 KB |
Output is correct |
15 |
Correct |
7 ms |
9712 KB |
Output is correct |
16 |
Correct |
7 ms |
9720 KB |
Output is correct |
17 |
Correct |
6 ms |
9676 KB |
Output is correct |
18 |
Correct |
7 ms |
9756 KB |
Output is correct |
19 |
Correct |
7 ms |
9680 KB |
Output is correct |
20 |
Correct |
6 ms |
9676 KB |
Output is correct |
21 |
Incorrect |
18 ms |
10612 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |