Submission #684419

#	Time	Username	Problem	Language	Result	Execution time	Memory
684419		dennisstar	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	1 ms	328 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;

int n;
vector<vector<int>> adj, ct, spt;

struct cent_decomposition {
	int n, rt;
	vector<vector<int>> adj, ct;
	vector<int> c1, c2, sub;

	void paint(int u, int p, int lv) {
		sub[u]=1;
		c1[u]=lv;
		for (int i:adj[u]) if (i!=p&&!c2[i]) paint(i, u, lv), sub[u]+=sub[i];
	}

	int get_cent(int u, int p, int s) {
		for (int i:adj[u]) if (i!=p&&!c2[i]&&sub[i]>s) return get_cent(i, u, s);
		return u;
	}

	void build() {
		int cnt=0, lv=0;
		while (cnt<n&&++lv) for (int i=1; i<=n; i++) if (!c2[i]&&c1[i]!=lv) {
			paint(i, 0, lv);
			int cent=get_cent(i, 0, sub[i]/2);
			c2[cent]=1;
			cnt++;
		}
	}

	void push(int u, int p, int a) {
		if (c1[u]==c1[a]+1) ct[a].emplace_back(u);
		for (int v:adj[u]) if (v!=p&&c1[v]>c1[a]) push(v, u, a);
	}

	cent_decomposition(int n) : n(n), ct(n+1), adj(n+1), c1(n+1), c2(n+1), sub(n+1) {
		for (int i=1, u, v; i<n; i++) cin>>u>>v, adj[u].emplace_back(v), adj[v].emplace_back(u);
		build();
		for (int i=1; i<=n; i++) push(i, 0, i);
		for (int i=1; i<=n; i++) if (c1[i]==1) rt=i;
		::adj=adj;
		::ct=ct;
	}
};

int ord;
vector<int> sz, dep, in, out, ans;

void dfs1(int u, int p) {
	if (u!=1) dep[u]=dep[p]+1;
	spt[u].emplace_back(p);
	for (int i=0; i<spt[spt[u][i]].size(); i++) spt[u].emplace_back(spt[spt[u][i]][i]);
	in[u]=++ord;
	for (int v:adj[u]) if (v!=p) dfs1(v, u), sz[u]+=sz[v];
	out[u]=ord;
}

int op(int u, int v) {
	if (in[u]<=in[v]&&out[v]<=out[u]) {
		for (int i=17; i>=0; i--) if (i<spt[v].size()&&dep[spt[v][i]]>dep[u]) v=spt[v][i];
		return n-sz[v];
	}
	return sz[u];
}

int dist(int u, int v) {
	if (dep[u]>dep[v]) swap(u, v);
	int rt=dep[v]-dep[u];
	for (int i=0; (1<<i)<=rt; i++) if (rt&(1<<i)) v=spt[v][i];
	if (u==v) return rt;
	for (int i=17; i>=0; i--) if (i<spt[u].size()&&spt[u][i]!=spt[v][i]) u=spt[u][i], v=spt[v][i], rt+=(1<<i+1);
	return rt+2;
}

void dfs2(int u) {
	vector<array<pair<int, int>, 2>> em;
	vector<int> to;
	auto ins = [&](int i, int v, int j) {
		if (em.size()<=i) em.resize(i+1);
		for (int k:{0, 1}) if (em[i][k].second==j) {
			em[i][k].first=max(em[i][k].first, v);
			if (em[i][0].first<em[i][1].first) swap(em[i][0], em[i][1]);
			return ;
		}
		if (em[i][0].first<v) em[i][1]=em[i][0], em[i][0]={v, j};
		else if (em[i][1].first<v) em[i][1]={v, j};
	};
	for (int v:ct[u]) dfs2(v);
	ins(1, 0, u);
	for (int v:ct[u]) {
		ct[v].emplace_back(v);
		for (int w:ct[v]) to.emplace_back(w);
		int xx=op(u, v);
		vector<pair<int, int>> im;
		for (int w:ct[v]) {
			int o=op(w, u);
			int d=dist(w, u);
			ans[min(xx, o)*2]=max(ans[min(xx, o)*2], d+1);
			im.emplace_back(o, d);
		}
		sort(im.rbegin(), im.rend());
		int mx=0;
		for (auto [i, w]:im) if (mx<w) mx=w, ins(i, w, v);
	}
	swap(to, ct[u]);
	for (int i=em.size()-1; i; i--) {
		ans[i*2]=max(ans[i*2], em[i][0].first+em[i][1].first+1);
		for (int j:{0, 1}) ins(i-1, em[i][j].first, em[i][j].second);
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin>>n;
	auto ct=cent_decomposition(n);
	sz.resize(n+1, 1);
	spt.resize(n+1);
	in=out=ans=dep=sz;
	dfs1(1, 0);
	dfs2(ct.rt);
	for (int i=(n&~1)-2; i>0; i-=2) ans[i]=max(ans[i+2], ans[i]);
	for (int i=1; i<=n; i++) cout<<ans[i]<<'\n';

	return 0;
}

Compilation message (stderr)

meetings2.cpp: In constructor 'cent_decomposition::cent_decomposition(int)':
meetings2.cpp:10:27: warning: 'cent_decomposition::ct' will be initialized after [-Wreorder]
   10 |  vector<vector<int>> adj, ct;
      |                           ^~
meetings2.cpp:10:22: warning:   'std::vector<std::vector<int> > cent_decomposition::adj' [-Wreorder]
   10 |  vector<vector<int>> adj, ct;
      |                      ^~~
meetings2.cpp:39:2: warning:   when initialized here [-Wreorder]
   39 |  cent_decomposition(int n) : n(n), ct(n+1), adj(n+1), c1(n+1), c2(n+1), sub(n+1) {
      |  ^~~~~~~~~~~~~~~~~~
meetings2.cpp: In function 'void dfs1(int, int)':
meetings2.cpp:55:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for (int i=0; i<spt[spt[u][i]].size(); i++) spt[u].emplace_back(spt[spt[u][i]][i]);
      |                ~^~~~~~~~~~~~~~~~~~~~~~
meetings2.cpp: In function 'int op(int, int)':
meetings2.cpp:63:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for (int i=17; i>=0; i--) if (i<spt[v].size()&&dep[spt[v][i]]>dep[u]) v=spt[v][i];
      |                                 ~^~~~~~~~~~~~~~
meetings2.cpp: In function 'int dist(int, int)':
meetings2.cpp:74:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |  for (int i=17; i>=0; i--) if (i<spt[u].size()&&spt[u][i]!=spt[v][i]) u=spt[u][i], v=spt[v][i], rt+=(1<<i+1);
      |                                ~^~~~~~~~~~~~~~
meetings2.cpp:74:106: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   74 |  for (int i=17; i>=0; i--) if (i<spt[u].size()&&spt[u][i]!=spt[v][i]) u=spt[u][i], v=spt[v][i], rt+=(1<<i+1);
      |                                                                                                         ~^~
meetings2.cpp: In lambda function:
meetings2.cpp:82:16: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<std::pair<int, int>, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   82 |   if (em.size()<=i) em.resize(i+1);
      |       ~~~~~~~~~^~~

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