Submission #387329

#	Time	Username	Problem	Language	Result	Execution time	Memory
387329		SeDunion	Event Hopping 2 (JOI21_event2)	C++17	0 / 100	11 ms	9956 KiB

event2

//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const int N = 2e5 + 66;
const int inf = 1e9;

inline void chk(int &a, int b) {a=max(a,b);}

vector<int>g[N];

int d[N], sz[N];
int tin[N], tout[N], timer, id[N];
void precalc(int v, int p = 1) {
	sz[v] = 1;
	tin[v] = timer++;
	id[tin[v]] = v;
	for (int to : g[v]) if (to != p) {
		d[to] = d[v] + 1;
		precalc(to, v);
		sz[v] += sz[to];
	}
	tout[v] = timer;
}

int D[N], ans[N], cur[N], D2[N];
int n, pq[N];

void dfs(int v, int p = -1, bool cl = 0) {
	int mx = -1; for (int to : g[v]) if (to != p) if (mx == -1 || sz[mx] < sz[to]) mx = to;
	for (int to : g[v]) if (to != p && to != mx) dfs(to, v, 1);
	if (mx != -1) dfs(mx, v, 0);
	int V = 2 * d[v];
	for (int to : g[v]) if (to != p && to != mx) {
		for (int l = tin[to] ; l < tout[to] ; ++ l) {
			int a = id[l];
			chk(cur[pq[a]], d[a] - V);
			chk(D2[pq[a]], d[a]);
		}
		for (int i = pq[to] ; i >= 1 ; -- i) {
			chk(ans[i], cur[i] + D[i]);
			chk(D[i], D2[i]);
			if (i < sz[to])
				chk(D[i], D[i + 1]);
			chk(cur[i - 1], cur[i]);
			cur[i] = -inf;
		}
	}
	chk(D[pq[v]], d[v]);
	for (int i = pq[v] ; i >= 1 ; -- i) {
		chk(D[i - 1], D[i]);
	}
	chk(ans[min(n >> 1, n - sz[v])], D[min(n >> 1, n - sz[v])] + 1 - d[v]);
	if (cl) {
		for (int i = 0 ; i <= pq[v] ; ++ i) {
			cur[i] = D[i] = D2[i] = -inf;
		}
	}
}

int H = 1;

int t[N * 4];

void modify(int l, int r, int value) {
  for (l += H, r += H; l < r; l >>= 1, r >>= 1) {
    if (l&1) t[l] = max(t[l], value), l++;
    if (r&1) --r, t[r] = max(t[r], value);
  }
}

int query(int p) {
  int res = -inf;
  for (p += H; p > 0; p >>= 1) res = max(res, t[p]);
  return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	while (H < n) H <<= 1;
	for (int i = 1 ; i < n ; ++ i) {
		int a, b;
		cin >> a >> b;
		g[a].emplace_back(b);
		g[b].emplace_back(a);
	}
	for (int i = 0 ; i < N ; ++ i) {
		D[i] = D2[i] = cur[i] = -inf;
	}
	precalc(1);
	const int HALF = n / 2;
	for (int i = 1 ; i <= n ; ++ i) {
		pq[i] = min(HALF, sz[i]);
	}
	dfs(1);
	{
		vector<pair<int,int>>vec;
		for (int i = 1 ; i <= n ; ++ i) {
			vec.emplace_back(n - sz[i], -i);
			vec.emplace_back(sz[i], i);
		}
		for (int i = 0 ; i < H * 2 ; ++ i) t[i] = -inf;
		sort(vec.rbegin(), vec.rend());
		for (auto [wsz, i] : vec) {
			if (i < 0) {
				i = -i;
				modify(tin[i], tout[i], -d[i] + 1);
			} else {
				int mx = query(tin[i]);
				ans[sz[i]] = max(ans[sz[i]], mx + d[i]);
			}
		}
	}
	for (int i = n ; i >= 1 ; -- i) {
		ans[i - 1] = max(ans[i - 1], ans[i]);
	}
	for (int i = 1 ; i <= n ; ++ i) {
		if (i % 2 == 1) {
			cout << 1 << "\n";
			continue;
		}
		cout << ans[i / 2] + 1 << "\n";
	}
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 1
• Subtask 3: 0 / 31
• Subtask 4: 0 / 61