#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef vector<int> vi;
#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()
int N, D;
struct Points{
int lazy; //add to the distance
set<pi> all_points; //distance, number
Points(){
lazy = 0;
// all_points.ins(mp(0, 1));
}
};
void print(Points* a){
cout << "printing all_points: " << "\n";
for(auto u: a->all_points){
u.f+=a->lazy;
cout << u.f << " " << u.s << "\n";
}
}
void insertPoint(Points* a, pi b){
// cout << "insertPoint: " << "\n";
// cout << "a: " << "\n";
// print(a);
// cout << "b: " << b.f << " " << b.s << "\n";
b.f-=a->lazy;
if(sz(a->all_points) == 0){
a->all_points.ins(b);
//print(a);
return;
}
auto it = a->all_points.lb(mp(b.f, 0));
if(it != a->all_points.end() && it->s >= b.s){
//print(a);
return;
}
it = a->all_points.lb(mp(b.f+1, 0));
while(it != a->all_points.begin()){
auto to_remove = prev(it);
if(to_remove->s <= b.s){
a->all_points.erase(to_remove);
}
else{
break;
}
}
a->all_points.ins(b);
// print(a);
}
void comb(Points* a, Points* b){ //insert b stuff into a
if(sz(a->all_points) < sz(b->all_points)){
swap(a->lazy, b->lazy);
swap(a->all_points, b->all_points);
}
//insert b stuff into a
for(auto u: b->all_points){
u.f+=b->lazy; //u.f is actual distance value now
insertPoint(a, u);
int needed_dist = D-u.f-a->lazy;
auto it = a->all_points.lb(mp(needed_dist, 0));
if(it != a->all_points.end()){
insertPoint(a, mp(min(u.f, (it->f)+a->lazy), u.s+it->s));
}
}
}
const int mx = 200005;
vi adj[mx];
Points* dp[mx];
void genDP(int node, int p = -1){
// cout << "node = " << node << "\n";
// cout << "node: " << node << "\n";
// cout.flush();
// cout << "dp[" << node << "]->all_points: " << "\n";
for(auto u: dp[node]->all_points){
u.f+=dp[node]->lazy;
// cout << u.f << " " << u.s << "\n";
}
for(auto u: adj[node]){
if(u == p) continue;
// cout << "u: " << u << "\n";
// cout.flush();
genDP(u, node);
dp[u]->lazy++;
comb(dp[node], dp[u]);
}
// cout << "dp[" << node << "]->all_points: " << "\n";
for(auto u: dp[node]->all_points){
u.f+=dp[node]->lazy;
// cout << u.f << " " << u.s << "\n";
}
Points* emp = new Points();
emp->all_points.ins(mp(0, 1));
comb(dp[node], emp);
// cout << "dp[" << node << "]->all_points: " << "\n";
for(auto u: dp[node]->all_points){
u.f+=dp[node]->lazy;
// cout << u.f << " " << u.s << "\n";
}
// cout << "node done: " << node << "\n";
// cout.flush();
}
int main(){
cin.tie(0)->sync_with_stdio(0);
for(int i = 0; i < mx; i++){
dp[i] = new Points();
}
cin >> N >> D;
for(int i = 1; i < N; i++){
int xi;
cin >> xi;
adj[xi].pb(i);
adj[i].pb(xi);
}
genDP(0);
assert(sz(dp[0]->all_points));
cout << dp[0]->all_points.begin()->s << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
19020 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
19004 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
19020 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
19004 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
19020 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
19004 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
