Submission #316168

#	Time	Username	Problem	Language	Result	Execution time	Memory
316168		kshitij_sodani	Papričice (COCI20_papricice)	C++14	50 / 110	286 ms	31736 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' 


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


void dfs(int no,int par=-1){
	ss[no]=1;
	for(auto j:adj[no]){
		if(j!=par){
			dfs(j,no);
			ss[no]+=ss[j];
		}
	}
}
set<int> pre[200001];
void re(int aa,int bb,int cc){
	ans=min(ans,max(max(abs(aa-bb),abs(bb-cc)),abs(aa-cc)));
}
int dfs2(int no,int 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]);
		}
	}
	int ma=0;
	int ind=-1;
	for(auto j:adj[no]){
		if(j!=par){
			int x=dfs2(j,no);
			if(pre[x].size()>ma){
				ma=pre[x].size();
				ind=x;
			}
		}
	}
	for(auto j:adj[no]){
		if(j!=par and 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(int i=0;i<n-1;i++){
		int 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 'int dfs2(int, int)':
papricice.cpp:49:20: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |    if(pre[x].size()>ma){
      |       ~~~~~~~~~~~~~^~~

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