oj.uz

Submission #316169

# Submission time Handle Problem Language Result Execution time Memory
316169 2020-10-25T16:23:46 Z kshitij_sodani Papričice (COCI20_papricice) C++14
50 / 110
 304 ms 33632 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' 


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;
	for(auto j:adj[no]){
		if(j!=par){
			llo 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(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

papricice.cpp: In function 'llo dfs2(llo, llo)':
papricice.cpp:49: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]
   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 150 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 11 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 150 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 11 ms 14592 KB Output is correct
11 Correct 267 ms 32888 KB Output is correct
12 Correct 304 ms 32872 KB Output is correct
13 Correct 245 ms 33632 KB Output is correct
14 Correct 259 ms 33272 KB Output is correct
15 Incorrect 281 ms 32760 KB Output isn't correct
16 Halted 0 ms 0 KB -