Submission #796515

#	Time	Username	Problem	Language	Result	Execution time	Memory
796515		MadokaMagicaFan	Cat in a tree (BOI17_catinatree)	C++14	51 / 100	277 ms	524288 KiB

catinatree

#include "bits/stdc++.h"
using namespace std;
using ll = long long;

const int N = 2e5;
int p[N];
int h[N];
int __n, d, inf;
vector<int> adj[N];

struct aint {
	int n;
	vector<int> f;

	aint(int _n)
	{
		n = _n;
		f.assign(n<<1, 0);
	}

	int query(int l, int r) {
		l += n;
		r += n+1;
		if (l >= 2*n-1) return 0;
		r = min(r, 2*n);
		int ans = 0;
		for (; l < r; l >>= 1, r >>= 1) {
			if (l&1) ans = max(ans, f[l++]);
			if (r&1) ans = max(ans, f[--r]);
		}

		return ans;
	}

	int getv(int x)
	{
		return f[x+n];
	}

	void upd(int x, int v)
	{
		x += n;
		for (f[x] = max(v, f[x]); x > 1; x>>=1) {
			f[x>>1] = max(f[x], f[x^1]);
		}
	}
};

vector<aint> t;
vector<int> lp[N];
int tp[N];
int mx1[N];
int mx2[N];

void
dfs(int x) {
	if (x) h[x] = h[p[x]] + 1;
	int _h, v, j;
	for (auto u : adj[x])
		dfs(u);
	// v = 1 + t[x].query(h[x]+d, inf);
	// t[x].upd(h[x], v);


	v = 0;
	for (int i = h[x] + d; i < __n; ++i)
		v = max(v, lp[x][i]);
	++v;
	lp[x][h[x]] = max(v, lp[x][h[x]]);


	if (!x) return;
	j = p[x];

	/*
	for (int z = __n-1; z >= h[x]; --z) {
		_h = max(2*h[j] + d - z, h[j]);
		t[j].upd(min(_h, z), t[j].query(_h, inf) + t[x].query(z, inf));
	}

	for (int z = h[x]; z < __n; ++z) {
		if (2*(z - h[j]) >= d)
			t[j].upd(z, t[x].query(z, inf) + t[j].query(z,inf));
	}

	for (int z = __n-1; z >= h[x]; --z) {
		t[j].upd(z, t[x].getv(z));
	}
	*/

	for (int i = 0; i < __n; ++i) tp[i] = 0;
	mx1[__n-1] = lp[x][__n-1];
	mx2[__n-1] = lp[j][__n-1];

	for (int i = __n-2; i >= h[j]; --i) {
		mx1[i] = max(mx1[i+1], lp[x][i]);
		mx2[i] = max(mx2[i+1], lp[j][i]);
	}

	for (int u = h[x]; u < __n; ++u) {
		tp[u] = max(mx1[u], mx2[u]);

		_h = max(2*h[j] + d - u, u);
		tp[u] = max(tp[u], mx1[u] + mx2[_h]);
		tp[u] = max(tp[u], mx2[u] + mx1[_h]);

		/*
		for (int z = u; z < __n; ++z) {
			_h = max(2*h[j] + d - z, h[j]);
			_h = max(u, _h);

			tp[u] = max(tp[u], mx1[z] + mx2[_h]);
		}
		*/
	}

	for (int u = __n-1; u >= h[j]; --u) {
		tp[u] = max(tp[u], tp[u+1]);
	}

	for (int i = h[j]; i < __n; ++i)
		lp[j][i] = tp[i];
}

int32_t main(int32_t argc, char *argv[])
{
	if (argc > 1) freopen(argv[1], "r", stdin);
	int n;
	cin >> n >> d;
	__n = n;
	inf = 2*n + 5;
	p[0] = 0;

	for (int i = 1; i < n; ++i) {
		cin >> p[i];
		adj[p[i]].push_back(i);
	}

	for (int i = 0; i <n; ++i)
		t.emplace(t.end() ,n);

	for (int i = 0; i <n; ++i)
		lp[i].assign(n, 0);

	h[0] = 0;

	dfs(0);

	/*
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j)
			cout << t[i].getv(j);
		cout<< endl;
	}

	cout << t[0].query(0, inf) << endl;;
	*/

	int ans = 0;
	for (int i = 0; i < n; ++i)
		ans = max(ans, lp[0][i]);

	cout << ans << endl;
}

Compilation message (stderr)

catinatree.cpp: In function 'int32_t main(int32_t, char**)':
catinatree.cpp:127:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |  if (argc > 1) freopen(argv[1], "r", stdin);
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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