#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ll mask){return __builtin_ctzll(mask);}
int logOf(ll mask){return __lg(mask);}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T& container, char separator = ' ', char finish = '\n'){
for(auto item: container) cout << item << separator;
cout << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
const int N = 2e5 + 69;
int n, d;
vector<pair<int, int>> graph[N];
int h[N];
void dfs(int u, int p){
for(auto v: graph[u]) if (v.first != p){
h[v.first] = h[u] + 1;
dfs(v.first, u);
}
}
namespace CD{
bitset<N> banned;
const int LOG_N = 18;
int sz[N], mi[N];
int h[N][LOG_N], centroid[N][LOG_N];
void init(){
for(int i = 1; i<=n; ++i) mi[i] = -1;
}
void find_sz(int u, int p){
sz[u] = 1;
for(auto v: graph[u]) if (!banned[v.second] && v.first != p){
find_sz(v.first, u);
sz[u] += sz[v.first];
}
}
int find_centroid(int u){
for(auto v: graph[u]) if (!banned[v.second] && sz[v.first] * 2 > sz[u]){
sz[u] -= sz[v.first];
sz[v.first] += sz[u];
return find_centroid(v.first);
}
return u;
}
void find_height(int u, int p, int layer){
for(auto v: graph[u]) if (!banned[v.second] && v.first != p){
h[v.first][layer] = h[u][layer] + 1;
centroid[v.first][layer] = centroid[u][layer];
find_height(v.first, u, layer);
}
}
void build_tree(int u, int layer){
find_sz(u, u);
u = find_centroid(u);
centroid[u][layer] = u;
find_height(u, u, layer);
for(auto v: graph[u]) if (!banned[v.second]){
banned[v.second] = true;
build_tree(v.first, layer + 1);
}
}
bool legit(int u){
for(int j = 0; j < LOG_N; ++j) if (centroid[u][j]){
int v = centroid[u][j];
if (h[u][j] <= mi[v]) return false;
}
return true;
}
void add(int u){
for(int j = 0; j < LOG_N; ++j) if (centroid[u][j]){
int v= centroid[u][j];
maximize(mi[v], d - h[u][j]);
}
}
}
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> d;
for(int i = 2; i<=n; ++i){
int p; cin >> p; p++;
graph[i].push_back({p, i-1});
graph[p].push_back({i, i-1});
}
d--;
dfs(1, 1);
vector<pair<int, int>> ligma;
for(int i = 1; i<=n; ++i) ligma.push_back({h[i], i});
sort(ALL(ligma), greater<pair<int, int>>());
vector<int> ans;
CD::init();
CD::build_tree(1, 0);
for(auto item: ligma) {
if (CD::legit(item.second)) {
CD::add(item.second);
ans.push_back(item.second);
}
}
cout << ans.size() << "\n";
// printArr(ans);
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
8796 KB |
Output is correct |
2 |
Correct |
2 ms |
8796 KB |
Output is correct |
3 |
Correct |
2 ms |
8872 KB |
Output is correct |
4 |
Correct |
2 ms |
8796 KB |
Output is correct |
5 |
Correct |
2 ms |
8876 KB |
Output is correct |
6 |
Correct |
2 ms |
8792 KB |
Output is correct |
7 |
Correct |
3 ms |
8796 KB |
Output is correct |
8 |
Correct |
2 ms |
8792 KB |
Output is correct |
9 |
Correct |
2 ms |
8792 KB |
Output is correct |
10 |
Correct |
2 ms |
8796 KB |
Output is correct |
11 |
Correct |
2 ms |
9052 KB |
Output is correct |
12 |
Correct |
2 ms |
8796 KB |
Output is correct |
13 |
Correct |
2 ms |
8796 KB |
Output is correct |
14 |
Correct |
2 ms |
8796 KB |
Output is correct |
15 |
Correct |
2 ms |
8796 KB |
Output is correct |
16 |
Correct |
2 ms |
8872 KB |
Output is correct |
17 |
Correct |
2 ms |
8796 KB |
Output is correct |
18 |
Correct |
2 ms |
8796 KB |
Output is correct |
19 |
Correct |
2 ms |
8796 KB |
Output is correct |
20 |
Correct |
1 ms |
8796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
8796 KB |
Output is correct |
2 |
Correct |
2 ms |
8796 KB |
Output is correct |
3 |
Correct |
2 ms |
8872 KB |
Output is correct |
4 |
Correct |
2 ms |
8796 KB |
Output is correct |
5 |
Correct |
2 ms |
8876 KB |
Output is correct |
6 |
Correct |
2 ms |
8792 KB |
Output is correct |
7 |
Correct |
3 ms |
8796 KB |
Output is correct |
8 |
Correct |
2 ms |
8792 KB |
Output is correct |
9 |
Correct |
2 ms |
8792 KB |
Output is correct |
10 |
Correct |
2 ms |
8796 KB |
Output is correct |
11 |
Correct |
2 ms |
9052 KB |
Output is correct |
12 |
Correct |
2 ms |
8796 KB |
Output is correct |
13 |
Correct |
2 ms |
8796 KB |
Output is correct |
14 |
Correct |
2 ms |
8796 KB |
Output is correct |
15 |
Correct |
2 ms |
8796 KB |
Output is correct |
16 |
Correct |
2 ms |
8872 KB |
Output is correct |
17 |
Correct |
2 ms |
8796 KB |
Output is correct |
18 |
Correct |
2 ms |
8796 KB |
Output is correct |
19 |
Correct |
2 ms |
8796 KB |
Output is correct |
20 |
Correct |
1 ms |
8796 KB |
Output is correct |
21 |
Correct |
2 ms |
9048 KB |
Output is correct |
22 |
Correct |
2 ms |
8796 KB |
Output is correct |
23 |
Correct |
2 ms |
8796 KB |
Output is correct |
24 |
Correct |
2 ms |
8796 KB |
Output is correct |
25 |
Correct |
3 ms |
9052 KB |
Output is correct |
26 |
Correct |
3 ms |
9116 KB |
Output is correct |
27 |
Correct |
2 ms |
9052 KB |
Output is correct |
28 |
Correct |
2 ms |
9148 KB |
Output is correct |
29 |
Correct |
3 ms |
9052 KB |
Output is correct |
30 |
Correct |
2 ms |
9052 KB |
Output is correct |
31 |
Correct |
3 ms |
9052 KB |
Output is correct |
32 |
Correct |
2 ms |
9052 KB |
Output is correct |
33 |
Correct |
2 ms |
9052 KB |
Output is correct |
34 |
Correct |
2 ms |
9144 KB |
Output is correct |
35 |
Correct |
2 ms |
9052 KB |
Output is correct |
36 |
Correct |
2 ms |
9052 KB |
Output is correct |
37 |
Correct |
2 ms |
9052 KB |
Output is correct |
38 |
Correct |
2 ms |
9052 KB |
Output is correct |
39 |
Correct |
3 ms |
9052 KB |
Output is correct |
40 |
Correct |
2 ms |
9052 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
8796 KB |
Output is correct |
2 |
Correct |
2 ms |
8796 KB |
Output is correct |
3 |
Correct |
2 ms |
8872 KB |
Output is correct |
4 |
Correct |
2 ms |
8796 KB |
Output is correct |
5 |
Correct |
2 ms |
8876 KB |
Output is correct |
6 |
Correct |
2 ms |
8792 KB |
Output is correct |
7 |
Correct |
3 ms |
8796 KB |
Output is correct |
8 |
Correct |
2 ms |
8792 KB |
Output is correct |
9 |
Correct |
2 ms |
8792 KB |
Output is correct |
10 |
Correct |
2 ms |
8796 KB |
Output is correct |
11 |
Correct |
2 ms |
9052 KB |
Output is correct |
12 |
Correct |
2 ms |
8796 KB |
Output is correct |
13 |
Correct |
2 ms |
8796 KB |
Output is correct |
14 |
Correct |
2 ms |
8796 KB |
Output is correct |
15 |
Correct |
2 ms |
8796 KB |
Output is correct |
16 |
Correct |
2 ms |
8872 KB |
Output is correct |
17 |
Correct |
2 ms |
8796 KB |
Output is correct |
18 |
Correct |
2 ms |
8796 KB |
Output is correct |
19 |
Correct |
2 ms |
8796 KB |
Output is correct |
20 |
Correct |
1 ms |
8796 KB |
Output is correct |
21 |
Correct |
2 ms |
9048 KB |
Output is correct |
22 |
Correct |
2 ms |
8796 KB |
Output is correct |
23 |
Correct |
2 ms |
8796 KB |
Output is correct |
24 |
Correct |
2 ms |
8796 KB |
Output is correct |
25 |
Correct |
3 ms |
9052 KB |
Output is correct |
26 |
Correct |
3 ms |
9116 KB |
Output is correct |
27 |
Correct |
2 ms |
9052 KB |
Output is correct |
28 |
Correct |
2 ms |
9148 KB |
Output is correct |
29 |
Correct |
3 ms |
9052 KB |
Output is correct |
30 |
Correct |
2 ms |
9052 KB |
Output is correct |
31 |
Correct |
3 ms |
9052 KB |
Output is correct |
32 |
Correct |
2 ms |
9052 KB |
Output is correct |
33 |
Correct |
2 ms |
9052 KB |
Output is correct |
34 |
Correct |
2 ms |
9144 KB |
Output is correct |
35 |
Correct |
2 ms |
9052 KB |
Output is correct |
36 |
Correct |
2 ms |
9052 KB |
Output is correct |
37 |
Correct |
2 ms |
9052 KB |
Output is correct |
38 |
Correct |
2 ms |
9052 KB |
Output is correct |
39 |
Correct |
3 ms |
9052 KB |
Output is correct |
40 |
Correct |
2 ms |
9052 KB |
Output is correct |
41 |
Correct |
87 ms |
44524 KB |
Output is correct |
42 |
Correct |
81 ms |
31684 KB |
Output is correct |
43 |
Correct |
86 ms |
30916 KB |
Output is correct |
44 |
Correct |
74 ms |
30928 KB |
Output is correct |
45 |
Correct |
74 ms |
30920 KB |
Output is correct |
46 |
Correct |
222 ms |
47084 KB |
Output is correct |
47 |
Correct |
206 ms |
45828 KB |
Output is correct |
48 |
Correct |
221 ms |
46036 KB |
Output is correct |
49 |
Correct |
207 ms |
45832 KB |
Output is correct |
50 |
Correct |
59 ms |
31176 KB |
Output is correct |
51 |
Correct |
58 ms |
31264 KB |
Output is correct |
52 |
Correct |
69 ms |
31172 KB |
Output is correct |
53 |
Correct |
157 ms |
46292 KB |
Output is correct |
54 |
Correct |
141 ms |
46280 KB |
Output is correct |
55 |
Correct |
152 ms |
46276 KB |
Output is correct |
56 |
Correct |
3 ms |
9304 KB |
Output is correct |
57 |
Correct |
13 ms |
16864 KB |
Output is correct |
58 |
Correct |
70 ms |
39212 KB |
Output is correct |
59 |
Correct |
234 ms |
53700 KB |
Output is correct |
60 |
Correct |
88 ms |
44964 KB |
Output is correct |
61 |
Correct |
118 ms |
44476 KB |
Output is correct |