Submission #523336

#	Time	Username	Problem	Language	Result	Execution time	Memory
523336		amunduzbaev	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	389 ms	49976 KiB

meetings2

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
 
const int N = 2e5 + 5;
vector<int> edges[N], cnt[N];
int sub[N], par[N][20], d[N];
int tin[N], tout[N], t;

void dfs(int u, int& C, int n, int p = -1){
	tin[u] = ++t, sub[u] = 1;
	for(int i=1;i<20;i++) par[u][i] = par[par[u][i-1]][i-1];
	for(auto x : edges[u]){
		if(x == p) continue;
		d[x] = d[u] + 1;
		par[x][0] = u;
		dfs(x, C, n, u);
		sub[u] += sub[x];
	}
	if(sub[u] > n / 2 && C == -1) C = u;
	tout[u] = t;
}

bool is(int a, int b){ return (tin[a] <= tin[b] && tout[b] <= tout[a]); }

int dis(int a, int b){
	//~ cout<<a<<" "<<b<<endl;
	if(is(a, b)) return d[b] - d[a];
	if(is(b, a)) return d[a] - d[b];
	int D = d[a] + d[b];
	for(int j=19;~j;j--){
		if(!is(par[a][j], b)) a = par[a][j];
	} a = par[a][0];
	return D - d[a] * 2;
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; 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);
	}
	
	int C = -1;
	par[1][0] = 1;
	dfs(1, C, n);
	
	vector<int> rr(n + 1);
	int a = C, b = C, d = 0;
	//~ cout<<C<<endl;
	par[C][0] = C;
	dfs(C, C, n);
	for(int i=1;i<=n;i++){
		cnt[sub[i]].push_back(i);
	}
	
	for(int i=n/2;i>0;i--){
		for(auto x : cnt[i]){
			//~ cout<<x<<" "<<a<<" "<<b<<" "<<d<<endl;;
			int da = dis(a, x), db = dis(b, x);
			if(da < db) swap(da, db), swap(a, b);
			if(da > d){
				assert(da == d + 1);
				d = da, b = x;
			} else if(db > d){
				assert(db == d + 1);
				d = db, a = x;
			}
		}
		
		rr[i] = d + 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: 80 / 80