제출 #756031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
756031		badont	Cat in a tree (BOI17_catinatree)	C++17	11 / 100	54 ms	90848 KiB

catinatree

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cassert>
#include <array>
#include <numeric>
#include <set>
#include <queue>
using namespace std;
using ll = long long;
#define pb push_back
template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
	cout << "["; 
	for (auto it = v.begin(); it != v.end();) {
		cout << *it;
		if (++it != v.end()) cout << ", ";
	}
	return cout << "]";
}

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif

#define all(x) x.begin(),x.end()
#define F0R(i,n) for (int i = 0; i < n; i++)

//benq
constexpr ll INF = 1e9;
struct Lazy {
    ll app, x;
    Lazy(ll a, ll b) : app(a), x(b) {}
    Lazy() : app(INF), x(-INF) {}
    Lazy& operator+=(const Lazy& o) {
        this->app = min(this->app, o.app);
        this->x = max(this->x, o.x);
        return *this;
    }
};
struct Info {
    ll max_depth, min_active;
    Info() : max_depth(-INF), min_active(INF) {}
    Info(ll md, ll ma) : max_depth(md), min_active(ma) {}
    friend Info operator+(const Info& a, const Info& b) {
        Info ret;
        ll val_1 = a.min_active - 2LL * a.max_depth;
        ll val_2 = b.min_active - 2LL * b.max_depth;
        if (val_1 < val_2) return a;
        else return b;
    }
    Info& operator+=(const Lazy& o) {
        this->max_depth = max(this->max_depth, o.x);
        this->min_active = min(this->min_active, o.app);
        return *this;
    }
};


template<class T, int SZ, class Lazy> struct LazySeg { 
	//zero indexed
	static_assert(__builtin_popcount(SZ) == 1); // SZ must be power of 2
	const T ID{}; T cmb(const T& a, const T& b) { return a+b; }
	T seg[2*SZ];
    Lazy lazy[2*SZ]; 
	LazySeg() { F0R(i,2*SZ) seg[i] = {}, lazy[i] = {}; }
	void push(int ind, int L, int R) { /// modify values for current node
		seg[ind] += lazy[ind]; // dependent on operation
		if (L != R) F0R(i,2) lazy[2*ind+i] += lazy[ind]; /// prop to children
		lazy[ind] = {}; 
	} // recalc values for current node
	void pull(int ind){seg[ind]=cmb(seg[2*ind],seg[2*ind+1]);}
	void build() { for (int i = SZ - 1; i >= 1; --i) pull(i); }
	void upd(int lo,int hi,const Lazy& inc,int ind=1,int L=0, int R=SZ-1) {
		push(ind,L,R); if (hi < L || R < lo) return;
		if (lo <= L && R <= hi) { 
			lazy[ind] += inc; push(ind,L,R); return; }
		int M = (L+R)/2; upd(lo,hi,inc,2*ind,L,M); 
		upd(lo,hi,inc,2*ind+1,M+1,R); pull(ind);
	}
	T query(int lo, int hi, int ind=1, int L=0, int R=SZ-1) {
		push(ind,L,R); if (lo > R || L > hi) return ID;
		if (lo <= L && R <= hi) return seg[ind];
		int M = (L+R)/2; return cmb(query(lo,hi,2*ind,L,M),
			query(lo,hi,2*ind+1,M+1,R));
	}
};

template<int SZ, bool VALS_IN_EDGES> struct HLD { 
	int N; vector<int> adj[SZ];
	int par[SZ], root[SZ], depth[SZ], sz[SZ], ti;
	int pos[SZ]; vector<int> rpos; // rpos not used but could be useful
	void ae(int x, int y) { adj[x].pb(y), adj[y].pb(x); }
	void dfsSz(int x) { 
		sz[x] = 1; 
		for (auto& y : adj[x]) {
			par[y] = x; depth[y] = depth[x]+1;
			adj[y].erase(find(all(adj[y]),x)); /// remove parent from adj list
			dfsSz(y); sz[x] += sz[y];
			if (sz[y] > sz[adj[x][0]]) swap(y,adj[x][0]);
		}
	}
	void dfsHld(int x) {
		pos[x] = ti++; rpos.pb(x);
		for (auto& y : adj[x]) {
			root[y] = (y == adj[x][0] ? root[x] : y);
			dfsHld(y); }
	}
	void init(int _N, int R = 0) { N = _N; 
		par[R] = depth[R] = ti = 0; dfsSz(R); 
		root[R] = R; dfsHld(R); 
	}
	int lca(int x, int y) {
		for (; root[x] != root[y]; y = par[root[y]])
			if (depth[root[x]] > depth[root[y]]) swap(x,y);
		return depth[x] < depth[y] ? x : y;
	}
	/// int dist(int x, int y) { // # edges on path
	/// 	return depth[x]+depth[y]-2*depth[lca(x,y)]; }
	LazySeg<Info,SZ,Lazy> tree; // segtree for sum
	template <class BinaryOp>
	void processPath(int x, int y, BinaryOp op) {
		for (; root[x] != root[y]; y = par[root[y]]) {
			if (depth[root[x]] > depth[root[y]]) swap(x,y);
			op(pos[root[y]],pos[y]); }
		if (depth[x] > depth[y]) swap(x,y);
		op(pos[x]+VALS_IN_EDGES,pos[y]); 
	}
	void modifyPath(int x, int y, const Lazy& v) { 
		processPath(x,y,[this,&v](int l, int r) { 
			tree.upd(l,r,v); }); }
	Info queryPath(int x, int y) { 
		Info res = {}; processPath(x,y,[this,&res](int l, int r) { 
			res = res + tree.query(l,r); });
		return res; }
};

HLD<1<<20, false> hld;

void solve() {
    ll n, d;
    cin >> n >> d;

    vector e(n, vector<ll>());
    for (int i = 0; i < n - 1; i++) {
        ll x; cin >> x;
        hld.ae(x, i + 1);
        e[x].pb(i + 1);
        e[i + 1].pb(x);
    }
    hld.init(n, 0);
    vector<ll> depth(n);
    auto dfs = [&](auto& dfs, ll g, ll p, ll d) -> void {
        depth[g] = d;
        hld.modifyPath(g, g, Lazy(INF, depth[g]));
        for (auto u : e[g]) if (u != p) {
            dfs(dfs, u, g, d + 1);
        }
    };
    dfs(dfs, 0, -1, 0);
    vector<ll> p(n);
    iota(all(p), 0);
    sort(all(p), [&](ll x, ll y) {
        return depth[x] > depth[y];
    });

    vector<ll> ans;
    for (auto u : p) {
        Info to_root = hld.queryPath(0, u);
        ll root_val = to_root.min_active - 2LL * to_root.max_depth;
        if (root_val + depth[u] >= d) {
            ans.pb(u);
            // activate u
            hld.modifyPath(0, u, Lazy(depth[u], -INF));
        }
    }

    sort(all(ans));
    cout << ans.size() << '\n';
    /*
    for (const auto& u : ans)
        cout << u + 1 << ' ';
    cout << '\n';
    */
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    solve();
    return 0;
}

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