Submission #759053

#	Time	Username	Problem	Language	Result	Execution time	Memory
759053		ymm	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	86 ms	20268 KiB

catinatree

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'010;
vector<int> A[N];
int par[N];
int st[N], ft[N];
int height[N];
pii srt[N];
int n, d;

void dfs(int v, int h, int &t)
{
	height[v] = h;
	st[v] = t++;
	for (int u : A[v])
		dfs(u, h+1, t);
	ft[v] = t;
}

int seg[2*N];
void up(int l, int r, int x)
{
	l += N;
	r += N;
	while (l < r) {
		if (l&1) seg[l++] = max(seg[l], x);
		if (r&1) seg[r] = max(seg[--r], x);
		l /= 2;
		r /= 2;
	}
}
int get(int i)
{
	i += N;
	int ans = INT_MIN;
	while (i > 0) {
		ans = max(ans, seg[i]);
		i /= 2;
	}
	return ans;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> d;
	Loop (i,1,n) {
		int p;
		cin >> p;
		par[i] = p;
		A[p].push_back(i);
	}
	int dard = 0;
	dfs(0, 0, dard);
	Loop (i,0,n)
		srt[i] = {height[i], i};
	sort(srt, srt+n, greater());
	fill(seg, seg+sizeof(seg)/sizeof(*seg), -N);
	int ans = 0;
	Loop (i,0,n) {
		int v = srt[i].second;
		if (height[v] - get(st[v]) < d)
			continue;
		++ans;
		int x = height[v];
		Loop (_,0,d) {
			up(st[v], ft[v], x);
			x -= 2;
			v = par[v];
		}
	}
	cout << ans << '\n';
}

Compilation message (stderr)

catinatree.cpp: In function 'void up(int, int, int)':
catinatree.cpp:32:17: warning: operation on 'l' may be undefined [-Wsequence-point]
   32 |   if (l&1) seg[l++] = max(seg[l], x);
      |                ~^~
catinatree.cpp:33:29: warning: operation on 'r' may be undefined [-Wsequence-point]
   33 |   if (r&1) seg[r] = max(seg[--r], x);
      |                             ^~~

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