Submission #802718

#	Time	Username	Problem	Language	Result	Execution time	Memory
802718		MohamedAliSaidane	Bodyguard (JOI21_bodyguard)	C++14	0 / 100	12 ms	19564 KiB

bodyguard

#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
typedef vector<int> vi;

#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(),(x).end()
const int nax = 2e5 + 5;

int n;
vi adj[nax];
int sz[20][nax], mark[nax], dis[20][nax], ans[nax];
struct node
{
	int maxi = 0;
	int maxi2 = 0;
	int sum = 0;
	int lazy1 = 0, lazy2 = 0;
};
node bss;
vector<node> st;
vi nodes[nax];

void mx(int p, int val)
{
	if(st[p].maxi <= val)
	{
		st[p].maxi2 = st[p].maxi;
		st[p].maxi = val;
	}
	else if(st[p].maxi2 < val)
	{
		st[p].maxi2 = val;
	}
	st[p].sum = max(st[p].sum, st[p].maxi + st[p].maxi2);

}
void mxlz(int p, int val)
{
	if(st[p].lazy1 <= val)
	{
		st[p].lazy2 = st[p].lazy1;
		st[p].lazy1 = val;
	}
	else if(st[p].lazy2 < val)
	{
		st[p].lazy2 = val;
	}

}
void propagate(int p, int l, int r)
{
	if(st[p].lazy1 != 0)
	{
		if(l != r)
		{
			mxlz(2 * p, st[p].lazy1);
			mxlz(2 * p, st[p].lazy2);
			mxlz(2 * p + 1, st[p].lazy1);
			mxlz(2 * p + 1, st[p].lazy2);
		}		
		mx(p, st[p].lazy1);
		mx(p, st[p].lazy2);
		st[p].lazy1 = st[p].lazy2 = 0;
	}
}
int query(int p, int l, int r, int i, int j)
{
	propagate(p, l, r);
	if(i > j)
		return 0;
	if(l >= i && r <= j)
		return st[p].sum;
	int m = (l + r)/2;
	return max(query(2 * p, l, m, i, min(j, m)),
				query(2 * p + 1, m + 1, r, max(i, m + 1), j));
}
void update(int p, int l, int r, int i, int j, int val)
{
	propagate(p, l, r);
	if(i > j)
		return ;
	if(l >= i && r <= j)
	{
		mxlz(p, val);
		propagate(p, l, r);
		return ;
	}
	int m = (l + r)/2;
	update(2 * p, l, m, i, min(j, m), val);
	update(2 * p + 1, m + 1, r, max(i, m + 1), j, val);
	st[p].sum = max(st[2 * p].sum, st[2 * p + 1].sum);
}
int getsz(int x, int d, int cur, int p = -1)
{
	sz[d][x] = 1;
	dis[d][x] = cur ;
	for(auto e: adj[x])
	{
		if(mark[e] || (e == p))
			continue;
		sz[d][x] += getsz(e, d, cur + 1, x);
	}
	return sz[d][x];
}
int get_centroid(int x, int d, int s, int p = -1)
{
	for(auto e: adj[x])
	{
		if(mark[e] || (e == p))
			continue;
		if(sz[d][e] > s/2)
			return get_centroid(e, d, s, x);
	}
	return x;
}
int centroid(int x, int d = 0)
{
	x = get_centroid(x, d, getsz(x, d, 0));
	getsz(x, d, 0);
	nodes[x].pb(x);
	mark[x] = 1;
	vi C;
	for(auto e: adj[x])
	{
		if(mark[e])
			continue;
		int c = centroid(e, d + 1);
		C.pb(c);
	}
	int k = 1;
	while(k < sz[d][x] + 1)
		k = (k << 1);
	st.assign(2 * k + 1, bss);
	for(auto c: C)
	{
		vector<pii> v;
		for(auto e: nodes[c])
		{
			nodes[x].pb(e);
			v.pb({dis[d][e], sz[d][e]});
			//cout << '\t' << x << ' ' << e << ' ' <<  dis[d][e] << ' ' << sz[d][e] << '\n';
		}
		nodes[c].clear();
		sort(all(v));
		reverse(all(v));
		int prev = 0;
		for(auto e: v)
		{
			if(e.ss <= prev)
				continue;
			update(1, 0, k - 1, prev + 1, e.ss, e.ff );
			//if(x == 3 && e.ss >= 3)
			///	cout << "\t\t" << e.ff << '\n';
			prev = e.ss;
			//cout << '\t'<<  x << ' ' << e.ff << ' ' << e.ss << '\n';
		}
	}
	
	for(int i = 1; i <= sz[d][x]; i++)
	{
		ans[i] = max(ans[i], query(1, 0, k - 1, i, sz[d][x]));
		//if(x == 2)
			//cout <<  query(1, 0, k - 1, i, sz[d][x]) << " ";
	}
	//cout << '\n';
	//cout << x << endl;
	
	return x;

}
void solve()
{
	cin >> n;
	for(int i = 1; i < n; i ++)
	{
		int a, b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	centroid(1);
	for(int i = 1; i <= n; i++)
	{
		if(i & 1)
			cout << 1 << '\n';
		else
			cout << ans[i/2]+ 1 << '\n';
	}
}
int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	/*
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif
	*/
	int tt = 1;
	while(tt--)
		solve();

}
/*
5
1 2
2 3
4 2
3 5
*/

• Subtask 1: 0 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 52