Submission #756160

#	Time	Username	Problem	Language	Result	Execution time	Memory
756160		badont	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	280 ms	41948 KiB

catinatree

#include<bits/stdc++.h>
using namespace std;
 
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
 
using ll = long long;
using ld = long double;
using pii = pair<ll,ll>;
 
#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
 
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 << "]";
}
 
//var 
ll T;
 
vector<ll> depth;
struct cmp {
	bool operator()(const ll& a, const ll& b) const {
		if (depth[a] == depth[b]) return a < b;
		return depth[a] > depth[b];
	};
};
 
void solve() {
	ll n, d; cin >> n >> d;
 
	vector e(n, vector<ll>());
	for (int i = 1; i < n; i++) {
		ll p; cin >> p;
		e[i].pb(p);
		e[p].pb(i);
	}
 
	depth.resize(n);
	auto dfs_depth = [&](auto& dfs, ll g, ll p, ll d) -> void {
		depth[g] = d;
		for (const auto& u : e[g]) if (u != p) {
			dfs(dfs, u, g, d + 1);
		}
	};
	dfs_depth(dfs_depth, 0, -1, 0);
	using Info = set<ll, cmp>;
 
	auto dfs = [&](auto& dfs, ll g, ll p) -> Info {
		Info ret;
		ret.insert(g);
		for (auto u : e[g]) if (u != p) { 
			Info o = dfs(dfs, u, g);
 
			if (o.size() > ret.size()) {
				swap(o, ret);
			}
 
			auto last = [](const auto& st) -> ll {
				return *prev(st.end());
			};
 
			ll need_at_least = 2LL * depth[g] + d;
			for (auto x : o) {
				while (!ret.empty() and 
					depth[last(ret)] + depth[x] < need_at_least and
					depth[last(ret)] < depth[x]) {
					ret.erase(last(ret));
				}
				if (ret.empty() or depth[last(ret)] + depth[x] >= need_at_least) {
					ret.insert(x);
				}
			}
			o.clear();
		}
		return ret;
	};
 
	Info ret = dfs(dfs, 0, -1);
	cout << ret.size() << "\n";
	/*
	for (const auto& u : ret)
		cout << u + 1 << " ";
	cout << "\n";
	*/
}
 
int main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0);
 
	T = 1;
	//cin >> T;
	FOR(t, T)
		solve();
 
	cout.flush();
	return 0;
}

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