Submission #434815

#	Time	Username	Problem	Language	Result	Execution time	Memory
434815		rqi	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	553 ms	203300 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 << "lazy value: " << a->lazy << "\n";
    cout << "printing all_points: " << "\n";
    for(auto u: a->all_points){
        u.f+=a->lazy;
        cout << u.f << " " << u.s << "\n";
    }
    cout.flush();
}

void insertPoint(Points* a, pi b){ //b is actual point
    // 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);
}

int getMinD(Points* a){
    if(sz(a->all_points) == 0){
        return 0;
    }
    return a->lazy+(prev(a->all_points.end()))->f;
}
 
void comb(Points* a, Points* b){ //insert b stuff into a
    if(getMinD(a) < getMinD(b)){
        swap(a->lazy, b->lazy);
        swap(a->all_points, b->all_points);
    }

    // cout << "comb: " << "\n";
    // cout << "a: " << "\n";
    // print(a);
    // cout << "b: " << "\n";
    // print(b);
    Points* c = new Points();

    for(auto A: a->all_points){
        A.f+=a->lazy;
        for(auto B: b->all_points){
            
            B.f+=b->lazy;

            if(A.f+B.f >= D){
                // cout << "c insert: " << min(A.f, B.f) <<" " << A.s+B.s << "\n";
                // cout << A.f << " " << B.f << " " << A.s << " " << B.s << "\n";
                insertPoint(c, mp(min(A.f, B.f), A.s+B.s));
            }
        }
    }

    for(auto A: a->all_points){
        A.f+=a->lazy;
        insertPoint(c, A);
    }
    for(auto B: b->all_points){
        B.f+=b->lazy;
        insertPoint(c, B);
    }

    
    // cout << "a: " << "\n";
    // print(a);
    // swap(a->lazy, c->lazy);
    // swap(a->all_points, c->all_points);


    set<pi> new_set;
    for(auto u: c->all_points){
        u.f-=a->lazy;
        new_set.ins(u);
    }
    c->all_points = new_set;
    c->lazy = a->lazy;
    // *a = *c;
    // return;
 
    //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 = max(D-u.f-a->lazy, u.f-a->lazy); //needed_dist is an a_dist
        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));
        }
    }

    // cout << "getMinD: " << getMinD(b) << "\n";
    for(auto u: a->all_points){
        u.f+=a->lazy;
        if(u.f > getMinD(b)) break;
        int needed_dist = max(D-u.f-b->lazy, u.f-b->lazy);
        auto it = b->all_points.lb(mp(needed_dist, 0));
        if(it != b->all_points.end()){
            to_add.pb(mp(min(u.f, (it->f)+b->lazy), u.s+it->s));
        }
    }
    for(auto u: to_add){
        // cout << "u: " << u.f << " " << u.s << "\n";
        insertPoint(a, u);
    }

    // cout << "a_res: " << "\n";
    // print(a);

    // cout << "c: " << "\n";
    // print(c);

    assert(a->lazy == c->lazy); 
    assert(a->all_points == c->all_points);

}
 
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: 49 / 49