Submission #434329

#	Time	Username	Problem	Language	Result	Execution time	Memory
434329		rqi	Cat in a tree (BOI17_catinatree)	C++14	0 / 100	23 ms	28492 KiB

catinatree

#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 insertPoint(Points* a, pi b){
	b.f-=a->lazy;
	if(sz(a->all_points) == 0){
		a->all_points.ins(b);
		return;
	}

	auto it = a->all_points.lb(mp(b.f, 0));
	if(it != a->all_points.end() && it->s >= b.s) return;

	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);
}

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.flush();
	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]);
	}

	Points* emp = new Points(); 
	comb(dp[node], emp);

	// 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 << prev(dp[0]->all_points.end())->s << "\n";
}

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