Submission #316173

#	Time	Username	Problem	Language	Result	Execution time	Memory
316173		kshitij_sodani	Papričice (COCI20_papricice)	C++14	110 / 110	462 ms	42744 KiB

papricice

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n' 


llo n;
vector<llo> adj[200001];
set<llo> cur;
llo ss[200001];
llo ans;


void dfs(llo no,llo par=-1){
	ss[no]=1;
	for(auto j:adj[no]){
		if(j!=par){
			dfs(j,no);
			ss[no]+=ss[j];
		}
	}
}
set<llo> pre[200001];
void re(llo aa,llo bb,llo cc){
	ans=min(ans,max(max(abs(aa-bb),abs(bb-cc)),abs(aa-cc)));
}
llo dfs2(llo no,llo par=-1){
	if(no!=0){
		auto j=cur.lower_bound((n-ss[no]+1)/2);
		
		if(j!=cur.end()){
			re(*j,ss[no],n-*j-ss[no]);
		}
		if(j!=cur.begin()){
			j--;
			re(*j,ss[no],n-*j-ss[no]);
		}
	}
	llo ma=0;
	llo ind=-1;
	vector<llo> pp;
	for(auto j:adj[no]){
		if(j!=par){
			llo x=dfs2(j,no);
			if(pre[x].size()>ma){
				ma=pre[x].size();
				ind=x;
			}
			pp.pb(x);
		}
	}
	for(auto j:pp){
		if(j!=ind){
			for(auto jj:pre[j]){
				pre[ind].insert(jj);
			}
		}
	}

	



	

	




	cur.insert(ss[no]);
	if(ind==-1){
		pre[no].insert(ss[no]);
		return no;
	}
	if(no!=0){
		auto j=pre[ind].lower_bound((ss[no]+1)/2);
		if(j!=pre[ind].end()){
			re(*j,ss[no]-*j,n-ss[no]);
		}
		if(j!=pre[ind].begin()){
			j--;
			re(*j,ss[no]-*j,n-ss[no]);
		}
	}

	pre[ind].insert(ss[no]);
	return ind;
	
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	ans=n;
	for(llo i=0;i<n-1;i++){
		llo aa,bb;
		cin>>aa>>bb;
		aa--;
		bb--;
		adj[aa].pb(bb);
		adj[bb].pb(aa);
	}
	dfs(0);
	dfs2(0);

	cout<<ans<<endl;


	return 0;
}

Compilation message (stderr)

papricice.cpp: In function 'llo dfs2(llo, llo)':
papricice.cpp:50:20: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'llo' {aka 'long long int'} [-Wsign-compare]
   50 |    if(pre[x].size()>ma){
      |       ~~~~~~~~~~~~~^~~

• Subtask 1: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 60 / 60