Submission #684961

#	Time	Username	Problem	Language	Result	Execution time	Memory
684961		arnold518	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	690 ms	75640 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const int INF = 1e9+7;

int N;
vector<int> adj[MAXN+10], VV[MAXN+10];

int sz[MAXN+10], dep[MAXN+10], par[MAXN+10];
int ans[MAXN+10];

vector<int> dfn;

void dfs(int now, int bef, int d)
{
	sz[now]=1;
	dep[now]=d;
	par[now]=bef;
	VV[now].push_back(dfn.size());
	dfn.push_back(now);
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs(nxt, now, d+1);
		VV[now].push_back(dfn.size());
		dfn.push_back(now);
		sz[now]+=sz[nxt];
	}
}

struct UF
{
	int par[MAXN+10], minv[MAXN+10], maxv[MAXN+10];
	void init()
	{
		for(int i=1; i<=N; i++)
		{
			par[i]=i;
			maxv[i]=minv[i]=dep[i];
		}
	}
	int Find(int x)
	{
		if(x==par[x]) return x;
		return par[x]=Find(par[x]);
	}
	void Union(int x, int y)
	{
		x=Find(x); y=Find(y);
		minv[x]=min(minv[x], minv[y]);
		maxv[x]=max(maxv[x], maxv[y]);
		par[y]=x;
	}
}uf;

struct Node
{
	int a, ab, aba, b, ba;
	Node() : a(-INF), ab(-INF), aba(-INF), b(-INF), ba(-INF) {}
};

Node operator + (const Node &p, const Node &q)
{
	Node ret;
	ret.a=max(p.a, q.a);
	ret.b=max(p.b, q.b);
	ret.ab=max({p.ab, q.ab, p.a+q.b});
	ret.ba=max({p.ba, q.ba, p.b+q.a});
	ret.aba=max({p.aba, q.aba, p.a+q.ba, p.ab+q.a});
	return ret;
}

struct SEG
{
	Node tree[MAXN*8+10];
	void update(int node, int tl, int tr, int p, int q)
	{
		if(tl==tr)
		{
			if(q==1) tree[node].a=dep[dfn[tl]];
			else if(q==2) tree[node].a=-INF;
			else tree[node].b=-2*dep[dfn[tl]];
			return;
		}
		int mid=tl+tr>>1;
		if(p<=mid) update(node*2, tl, mid, p, q);
		else update(node*2+1, mid+1, tr, p, q);
		tree[node]=tree[node*2]+tree[node*2+1];
	}
	int val() { return tree[1].aba; }
}seg;

int main()
{
	scanf("%d", &N);
	for(int i=1; i<N; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	dfs(1, 1, 1);

	vector<pii> V;
	int t=0;
	for(int i=2; i<=N; i++)
	{
		int p=sz[i], q=sz[par[i]];
		V.push_back({min({p, N-p, q, N-q}), i});
		t=max(t, min(p, N-p));
	}

	sort(V.begin(), V.end(), greater<pii>());

	uf.init();

	int val=1;
	for(int i=N/2, j=0; i>=1; i--)
	{
		if(t>=i) val=max(val, 2);
		for(; j<V.size() && V[j].first>=i; j++)
		{
			int u=V[j].second;
			uf.Union(u, par[u]);
			u=uf.Find(u);
			val=max(val, uf.maxv[u]-uf.minv[u]+2);
		}
		ans[i]=val;
	}

	V.clear();
	for(int i=1; i<=N; i++) V.push_back({sz[i], i});
	sort(V.begin(), V.end(), greater<pii>());

	for(int i=N/2, j=0; i>=1; i--)
	{
		for(; j<V.size() && V[j].first>=i; j++)
		{
			if(V[j].second!=1) seg.update(1, 0, dfn.size()-1, VV[par[V[j].second]].front(), 2);
			for(auto it : VV[V[j].second]) seg.update(1, 0, dfn.size()-1, it, 0);
			seg.update(1, 0, dfn.size()-1, VV[V[j].second].front(), 1);
		}
		ans[i]=max(ans[i], seg.val()+1);
		//printf("!%d\n", seg.val());
	}

	for(int i=1; i<=N; i++)
	{
		if(i%2) printf("1\n");
		else printf("%d\n", ans[i/2]);
	}
}

Compilation message (stderr)

meetings2.cpp: In member function 'void SEG::update(int, int, int, int, int)':
meetings2.cpp:90:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   90 |   int mid=tl+tr>>1;
      |           ~~^~~
meetings2.cpp: In function 'int main()':
meetings2.cpp:128:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |   for(; j<V.size() && V[j].first>=i; j++)
      |         ~^~~~~~~~~
meetings2.cpp:144:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |   for(; j<V.size() && V[j].first>=i; j++)
      |         ~^~~~~~~~~
meetings2.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
meetings2.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~

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