Submission #434597

#	Time	Username	Problem	Language	Result	Execution time	Memory
434597		rqi	Cat in a tree (BOI17_catinatree)	C++14	51 / 100	120 ms	49072 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> 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()
 
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
    vpi to_add;
    for(auto u: b->all_points){
        u.f+=b->lazy; //u.f is actual distance value now
        to_add.pb(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()){
            to_add.pb(mp(min(u.f, (it->f)+a->lazy), u.s+it->s));
        }
    }

    for(auto u: to_add){
        insertPoint(a, u);
    }
}
 
const int mx = 200005;
 
vi adj[mx];
Points* dp[mx];
 
void genDP(int node, int p = -1){
    // cout << "node = " << node << "\n";
    // cout.flush();

    // cout << "dp[" << node << "]->all_points: " << "\n";
    // print(dp[node]);

    for(auto u: adj[node]){
        if(u == p) continue;
        
        genDP(u, node);
        dp[u]->lazy++;
        comb(dp[node], dp[u]);

        // cout << "u: " << u << "\n";
        // cout.flush();
        // cout << "dp[" << node << "]->all_points: " << "\n";
        // print(dp[node]);
    }

    // cout << "dp[" << node << "]->all_points: " << "\n";
    // print(dp[node]);

    Points* emp = new Points(); 
    emp->all_points.ins(mp(0, 1));
    comb(dp[node], emp);

    // cout << "dp[" << node << "]->all_points: " << "\n";
    // print(dp[node]);

    // 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";
}

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 0 / 49