Submission #1249110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249110		kamrad	Meetings 2 (JOI21_meetings2)	C++20	100 / 100	354 ms	25236 KiB

meetings2

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

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")

using ll  = long long;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pi3 = pair<pii, int>;

#define IOS               ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define F                 first
#define S                 second
#define sz(x)             x.size()
#define all(x)            x.begin(), x.end()
#define pb                push_back
#define cl                clear
#define minr(a, b)        a = min(a, b);
#define maxr(a, b)        a = max(a, b);
#define shit              cout << "shit\n" << flush;
#define tl                while(1&1) continue;
#define FOR(i, st, nd)    for(int i = st; i <= nd; i++)
#define rand(l, r)        uniform_int_distribution<int64_t>(l,r)(rng)
random_device device;     default_random_engine rng(device());

const int Mod    = 1e9 + 7; //998244353;
const int LG     = 64;
const int SQ     = 500;
const int Inf    = 2e9 + 10;
const int maxN   = 2e5 + 10;

int n;
int a[maxN];
int b[maxN];
int ans[maxN];
int sts[maxN];

bool mark[maxN];

vector <int> neighb[maxN];

void cent(int u, int p, int CurSz, int &c) {
	sts[u] = 1;
	for(auto v : neighb[u]) {
		if(v == p or mark[v])
			continue;
		cent(v, u, CurSz, c);
		sts[u] += sts[v];
	}

	bool check = false;
	if(sts[u] >= (CurSz+1)/2) {
		check = true;
		for(auto v : neighb[u]) {
			if(v == p or mark[v])
				continue;

			if(sts[v] > CurSz/2) {
				check = false;
				break;
			}
		}
	}
	if(check)
		c = u;
}

void calc(int u, int p, int h) {
	a[sts[u]] = max(h, a[sts[u]]);
	for(auto v : neighb[u]) {
		if(v != p and !mark[v]) {
			calc(v, u, h+1);
		}
	}
}

void solve(int u, int CurSz) {
	if(CurSz == 1) {
		return;
	}

	int c;
	int tmp;
	cent(u, u, CurSz, c);
	cent(c, c, CurSz, tmp);
	c = u;
	c = tmp;

	mark[c] = true;

	for(int i = 1; i <= CurSz; i++)
		b[i] = 0;
	for(auto v : neighb[c]) {
		if(!mark[v]) {
			for(int i = 1; i <= sts[v]; i++)
				a[i] = 0;
			calc(v, c, 1);

			for(int i = sts[v]-1; i >= 1; i--)
				maxr(a[i], a[i+1]);

			for(int i = 1; i <= sts[v]; i++) {
				maxr(ans[i], a[i]+b[i]+1);
				maxr(b[i], a[i]);
			}	
		}
	}
	for(auto v : neighb[c])
		if(!mark[v])
			solve(v, sts[v]);
}

int main() {
	IOS;

	cin >> n;
	for(int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		neighb[u].pb(v);
		neighb[v].pb(u);
	}

	solve(1, n);
	for(int i = 1; i <= n; i++) {
		if(i%2)
			cout << 1 << "\n";
		else
			cout << max(ans[i/2], 1) << "\n";
	}
}

• Subtask 1: 4 / 4
• Subtask 2: 16 / 16
• Subtask 3: 80 / 80