제출 #1139523

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139523		Math4Life2020	Meetings 2 (JOI21_meetings2)	C++20	100 / 100	882 ms	213140 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 = 25; 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 sts0[Nm][E]; //from centroid decomp tree nodes
vector<pii> xupd[Nm];
ll sts[Nm]; //subtree size
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;
	sts0[x][e]=sts[x];
	if (x != ctr) {
		xupd[sts[x]].push_back({x,e});
	}
	//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";
	getsz(ctr);
	wdist(ctr,e,0,ctr,-1);
	found[ctr]=1;
	for (ll y: adj[ctr]) {
		if (!found[y]) {
			bldTree(y,e+1);
		}
	}
}

void updp(pii p0) {
	ll x = p0.first; ll e = p0.second;
	mem[cdp[x][e]]=wmem(mem[cdp[x][e]],cdp[x][e+1],dpt[x][e]);
	rmem(cdp[x][e]);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll N; cin >> N;
	for (ll i=0;i<Nm;i++) {
		ansf[i]=1;
		mem[i]={-2,0,-3,-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);
	for (ll k=K;k>=1;k--) {
		for (pii p0: xupd[k]) {
			updp(p0);
		}
		ansf[2*k]=ans;
	}
	for (ll i=1;i<=N;i++) {
		cout << ansf[i]<<"\n";
	}
}

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