Submission #796492

#	Time	Username	Problem	Language	Result	Execution time	Memory
796492		MadokaMagicaFan	Cat in a tree (BOI17_catinatree)	C++14	0 / 100	3 ms	4948 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;

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

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

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

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

Compilation message (stderr)

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

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