Submission #1139500

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139500		Math4Life2020	Meetings 2 (JOI21_meetings2)	C++20	0 / 100	38 ms	84924 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = 2e5+5; const ll E = 45; const ll INF = 1e18;

vector<ll> adj[Nm];
ll ansf[Nm];
ll ans = 1; //current answer
vector<bool> found(Nm,false);
ll cdp[Nm][E]; //centroid decomp parent
ll dpt[Nm][E]; //centroid decomp parent distance
ll sts[Nm]; //subtree size
ll sts0[Nm]; //from root of centroid decomp tree
array<ll,4> mem[Nm];
//{x of max, val of max, x of 2max, val of 2max}

void rmem(ll x) {
	if (x<0) {
		assert(1==2);
	}
	ans = max(ans,1+mem[x][1]+mem[x][3]);
}

array<ll,4> wmem(array<ll,4> mem0, ll xc, ll vc) {
	if (xc<0) {
		return mem0;
	}
	if (xc==mem0[0]) {
		mem0[1]=max(mem0[1],vc);
	} else if (xc==mem0[2]) {
		mem0[3]=max(mem0[3],vc);
	} else {
		if (vc > mem0[3]) {
			mem0[2]=xc;
			mem0[3]=vc;
		}
	}
	if (mem0[1]<mem0[3]) {
		return {mem0[2],mem0[3],mem0[0],mem0[1]};
	}
	return mem0;
}

ll getsz(ll x, ll prt=-1) { //{current node, parent}
//get subtree size
	sts[x]=1;
	for (ll y: adj[x]) {
		if (!found[y] && y!=prt) {
			sts[x]+=getsz(y,x);
		}
	}
	return sts[x];
}

ll getct(ll x, ll sz0, ll prt=-1) {
//get centroid
	for (ll y: adj[x]) {
		if (!found[y] && y!=prt) {
			if (2*sts[y]>=sz0) {
				return getct(y,sz0,x);
			}
		}
	}
	return x;
}

void wdist(ll x, ll e, ll d0, ll ctr, ll prt=-1) {
//write distances
	cdp[x][e]=ctr;
	dpt[x][e]=d0;
	//cout << "x,e,dpt="<<x<<","<<e<<","<<dpt[x][e]<<"\n";
	for (ll y: adj[x]) {
		if (!found[y] && y!=prt) {
			wdist(y,e,d0+1,ctr,x);
		}
	}
}

void bldTree(ll r, ll e) {
	ll sz0 = getsz(r);
	ll ctr = getct(r,sz0);
	//cout << "ctr,e="<<ctr<<","<<e<<"\n";
	wdist(ctr,e,0,ctr,-1);
	if (e==0) {
		getsz(ctr);
		for (ll i=0;i<Nm;i++) {
			sts0[i]=sts[i];
		}
	}
	found[ctr]=1;
	for (ll y: adj[ctr]) {
		if (!found[y]) {
			bldTree(y,e+1);
		}
	}
}

void updp(ll x) {
	for (ll e=0;e<E;e++) {
		ll p0 = cdp[x][e];
		if (p0==-1 || cdp[x][e+1]==-1) {
			continue;
		}
		//cout << "x,e,dpt="<<x<<","<<e<<","<<dpt[x][e]<<"\n";
		mem[p0]=wmem(mem[p0],cdp[x][e+1],dpt[x][e]);
		rmem(p0);
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll N; cin >> N;
	if (N==1) {
		cout << "1\n"; exit(0);
	}
	if (N==2) {
		cout << "1\n2\n"; exit(0);
	}
	for (ll i=0;i<Nm;i++) {
		ansf[i]=1;
		mem[i]={-2,0,-2,-INF};
		for (ll e=0;e<E;e++) {
			cdp[i][e]=-1;
		}
	}
	for (ll i=0;i<(N-1);i++) {
		ll a,b; cin >> a >> b; a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	bldTree(0,0);
	ll K = (N/2);
	vector<ll> xupd[N+1];
	for (ll i=0;i<N;i++) {
		xupd[sts0[i]].push_back(i);
	}
	for (ll k=K;k>=1;k--) {
		for (ll x: xupd[k]) {
			updp(x);
		}
		ansf[2*k]=ans;
	}
	for (ll i=1;i<=N;i++) {
		cout << ansf[i]<<"\n";
	}
}

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