Submission #523310

#	Time	Username	Problem	Language	Result	Execution time	Memory
523310		amunduzbaev	Meetings 2 (JOI21_meetings2)	C++17	20 / 100	4077 ms	92476 KiB

meetings2

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
 
const int N = 2e5 + 5;
vector<int> edges[N], S[N];
int used[N], ss[N], rr[N];
int sub[N], n, d[N];
 
void dff(int u, int p = -1){
	ss[u] = 1;
	for(auto x : edges[u]){
		if(x == p) continue;
		dff(x, u);
		ss[u] += ss[x];
	}
}
 
void dfs(int u, int& C, int n, int p = -1){
	sub[u] = 1;
	if(p == -1) d[u] = 0;
	for(auto x : edges[u]){
		if(x == p) continue;
		if(!used[x]){
			d[x] = d[u] + 1;
			dfs(x, C, n, u);
			sub[u] += sub[x];
		} else {
			if(ss[u] > ss[x]) sub[u] += ss[x];
			else sub[u] += (::n - ss[u]);
		}
	}
	if(sub[u] > n / 2 && C == -1) C = u;
}
 
void get(int u, vector<int>& tt, int p = -1){
	tt.push_back(u);
	for(auto x : edges[u]){
		if(used[x] || x == p) continue;
		get(x, tt, u);
	}
}

struct ST{
	int tree[N << 2];
	void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = v; return; }
		int m = (lx + rx) >> 1;
		if(i <= m) sett(i, v, lx, m, x<<1);
		else sett(i, v, m+1, rx, x<<1|1);
		tree[x] = max(tree[x<<1], tree[x<<1|1]);
	}
	
	void umax(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = max(tree[x], v); return; }
		int m = (lx + rx) >> 1;
		if(i <= m) umax(i, v, lx, m, x<<1);
		else umax(i, v, m+1, rx, x<<1|1);
		tree[x] = max(tree[x<<1], tree[x<<1|1]);
	}
	
	int get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -1e9;
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		return max(get(l, r, lx, m, x<<1), get(l, r, m+1, rx, x<<1|1));
	}
}tree;

void dec(int u, int n){
	int C = -1;
	dfs(u, C, n), dfs(C, C, n);
	
	vector<int> tot;
	for(auto v : edges[C]){
		if(used[v]) continue;
		S[v].clear(); get(v, S[v], C);
		for(auto x : S[v]){
			//~ cout<<sub[x]<<" "<<sub[C] - sub[v]<<endl;
			rr[sub[x]] = max(rr[sub[x]], tree.get(sub[x], N) + d[x] + 1);
			rr[min(sub[x], sub[C] - sub[v])] = 
			max(rr[min(sub[x], sub[C] - sub[v])], d[x] + 1);
		} for(auto x : S[v]) tree.umax(sub[x], d[x]), tot.push_back(x);
	} for(auto x : tot) tree.sett(sub[x], -2e9);
	
	reverse(edges[C].begin(), edges[C].end());
	
	for(auto v : edges[C]){
		if(used[v]) continue;
		for(auto x : S[v]){
			//~ cout<<sub[x]<<" "<<x<<" "<<d[x]<<" "<<tree.get(sub[x], N)<<endl;
			rr[sub[x]] = max(rr[sub[x]], tree.get(sub[x], N) + d[x] + 1);
		} for(auto x : S[v]) tree.umax(sub[x], d[x]);
	} for(auto x : tot) tree.sett(sub[x], -2e9);
	
	used[C] = 1;
	for(auto x : edges[C]){
		if(used[x]) continue;
		dec(x, (int)S[x].size());
	}
}
 
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	memset(tree.tree, 128, sizeof tree.tree);
	cin>>n;
	for(int i=1;i<n;i++){
		int a, b; cin>>a>>b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	
	dff(1);
	dec(1, n);
	rr[n] = 1;
	//~ for(int i=1;i<=n;i++) cout<<rr[i]<<" ";
	//~ cout<<endl;
	for(int i=n;i>0;i--) rr[i] = max(rr[i], rr[i+1]);
	for(int i=1;i<=n;i++){
		if(i&1) cout<<1<<"\n";
		else cout<<rr[i/2]<<"\n";
	}
}

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