oj.uz

Submission #316168

# Submission time Handle Problem Language Result Execution time Memory
316168 2020-10-25T16:21:01 Z kshitij_sodani Papričice (COCI20_papricice) C++14
50 / 110
 286 ms 31736 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 10 ms 14464 KB Output is correct
5 Correct 10 ms 14464 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 10 ms 14464 KB Output is correct
5 Correct 10 ms 14464 KB Output is correct
6 Correct 11 ms 14592 KB Output is correct
7 Correct 11 ms 14592 KB Output is correct
8 Correct 11 ms 14592 KB Output is correct
9 Correct 11 ms 14592 KB Output is correct
10 Correct 12 ms 14592 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Correct 10 ms 14464 KB Output is correct
4 Correct 10 ms 14464 KB Output is correct
5 Correct 10 ms 14464 KB Output is correct
6 Correct 11 ms 14592 KB Output is correct
7 Correct 11 ms 14592 KB Output is correct
8 Correct 11 ms 14592 KB Output is correct
9 Correct 11 ms 14592 KB Output is correct
10 Correct 12 ms 14592 KB Output is correct
11 Correct 259 ms 31080 KB Output is correct
12 Correct 286 ms 31096 KB Output is correct
13 Correct 239 ms 31736 KB Output is correct
14 Correct 245 ms 31352 KB Output is correct
15 Incorrect 268 ms 31096 KB Output isn't correct
16 Halted 0 ms 0 KB -