Submission #543282

#	Time	Username	Problem	Language	Result	Execution time	Memory
543282		cheissmart	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	395 ms	42296 KiB

meetings2

#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 2e5 + 7;

vi G[N];
int sz[N], n;

void get_c(int u, int& c, int p = 0) {
	int mx = 0;
	sz[u] = 1;
	for(int v:G[u]) if(v != p) {
		get_c(v, c, u);
		sz[u] += sz[v];
		mx = max(mx, sz[v]);
	}
	mx = max(mx, n - sz[u]);
	if(mx * 2 <= n) c = u;
}

V<pi> aux;

int p[N][20], d[N];

void dfs(int u, int pa = 0) {
	sz[u] = 1;
	p[u][0] = pa;
	for(int i = 1; i < 20; i++)
		p[u][i] = p[p[u][i - 1]][i - 1];
	for(int v:G[u]) if(v != pa) {
		d[v] = d[u] + 1;
		dfs(v, u);
		sz[u] += sz[v];
	}
	aux.EB(sz[u], u);
}

int lca(int u, int v) {
	if(d[u] > d[v]) swap(u, v);
	for(int i = 19; i >= 0; i--)
		if((d[v] - d[u]) >> i & 1)
			v = p[v][i];
	if(u == v) return u;
	for(int i = 19; i >= 0; i--)
		if(p[u][i] != p[v][i])
			u = p[u][i], v = p[v][i];
	return p[u][0];
}
int dist(int u, int v) {
	return d[u] + d[v] - d[lca(u, v)] * 2;
}

int ans[N];

signed main()
{
	IO_OP;
	
	cin >> n;
	for(int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		G[u].PB(v);
		G[v].PB(u);
	}
	int c; get_c(1, c);	
	
	dfs(c);
	sort(ALL(aux));
	int a = -1, b = -1;
	for(int i = n / 2 * 2; i >= 2; i -= 2) {
		while(SZ(aux) && aux.back().F >= i / 2) {
			int u = aux.back().S;
			aux.pop_back();
			if(a == -1) a = u;
			else if(b == -1) b = u;
			else {
				if(dist(a, u) > dist(a, b) || dist(b, u) > dist(a, b)) {
					if(dist(a, u) > dist(b, u)) b = u;
					else a = u;
				}
			}
		}
		if(a != -1 && b != -1) ans[i] = dist(a, b);
	}
	for(int i = 1; i <= n; i++)
		cout << ans[i] + 1 << '\n';
}

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