oj.uz

Submission #949887

# Submission time Handle Problem Language Result Execution time Memory
949887 2024-03-19T20:13:47 Z amirhoseinfar1385 Meetings 2 (JOI21_meetings2) C++17
0 / 100
 12 ms 30044 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=200000+10,lg=19;
int n,lca[lg][maxn],high[maxn],timea=0,sz[maxn];
vector<int>adj[maxn];
vector<pair<int,int>>ady[maxn];
pair<int,int>stf[maxn];

bool zird(int u,int v){
	return stf[v].first<=stf[u].first&&stf[v].second>=stf[u].second;
}

int getlca(int u,int v){
	if(zird(u,v)){
		return v;
	}
	if(zird(v,u)){
		return u;
	}
	for(int i=lg-1;i>=0;i--){
		if(lca[i][u]!=0&&zird(v,lca[i][u])==0){
			u=lca[i][u];
		}
	}
	return lca[0][u];
}

int dis(int u,int v){
	int uv=getlca(u,v);
	return high[u]+high[v]-2*high[uv];
}

struct dsu{
	int res=1;
	int par[maxn];
	pair<int,int>di[maxn];
	dsu(){
		for(int i=0;i<maxn;i++){
			par[i]=i;
			di[i]=make_pair(i,i);
		}
	}
	int root(int u){
		if(par[u]==u){
			return u;
		}
		return par[u]=root(par[u]);
	}
	void con(int u,int v){
		u=root(u),v=root(v);
		if(u!=v){
			par[v]=u;
			pair<int,int>hey;
			int mx=-1;
			vector<int>nag={di[u].first,di[u].second,di[v].first,di[v].second};
			for(int i=0;i<4;i++){
				for(int j=i+1;j<4;j++){
					if(dis(nag[i],nag[j])>mx){
						mx=dis(nag[i],nag[j]);
						hey=make_pair(nag[i],nag[j]);
					}
				}
			}
			di[u]=hey;
			res=max(res,mx);
		}
	}
}ds;

void vorod(){
	cin>>n;
	for(int i=0;i<n-1;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
}

void callca(){
	for(int i=1;i<lg;i++){
		for(int j=0;j<maxn;j++){
			lca[i][j]=lca[i-1][lca[i-1][j]];
		}
	}
}

void dfs(int u,int par=-1){
	sz[u]=1;
	timea++;
	stf[u].first=timea;
	for(auto x:adj[u]){
		if(x==par){
			continue;
		}
		high[x]=high[u]+1;
		lca[0][x]=u;
		dfs(x,u);
		sz[u]+=sz[x];
		ady[min(sz[x],n-sz[x])].push_back(make_pair(u,x));
	}
	stf[u].second=timea;
}

void pre(){
	dfs(1);
	callca();
}

void solve(){
	vector<int>res;
	for(int i=n;i>=1;i--){
		if(i&1){
			res.push_back(1);
			continue;
		}
		for(auto x:ady[i/2]){
			ds.con(x.first,x.second);
		}
		res.push_back(ds.res+1);
	}
	reverse(res.begin(),res.end());
	for(auto x:res){
		cout<<x<<"\n";
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("inp.txt","r",stdin);
	vorod();
	pre();
	solve();
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 29020 KB Output is correct
2 Correct 8 ms 30044 KB Output is correct
3 Correct 8 ms 30044 KB Output is correct
4 Correct 10 ms 30044 KB Output is correct
5 Incorrect 8 ms 30044 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 29020 KB Output is correct
2 Correct 8 ms 30044 KB Output is correct
3 Correct 8 ms 30044 KB Output is correct
4 Correct 10 ms 30044 KB Output is correct
5 Incorrect 8 ms 30044 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 29020 KB Output is correct
2 Correct 8 ms 30044 KB Output is correct
3 Correct 8 ms 30044 KB Output is correct
4 Correct 10 ms 30044 KB Output is correct
5 Incorrect 8 ms 30044 KB Output isn't correct
6 Halted 0 ms 0 KB -