Submission #446269

#	Time	Username	Problem	Language	Result	Execution time	Memory
446269		Antekb	Papričice (COCI20_papricice)	C++14	50 / 110	1076 ms	24756 KiB

papricice

#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int N=2e5+5;
multiset<int> S, S2;//S-subtree, S2=tree\subtree
int siz[N], par[N];
vector<int> E[N];
void dfs_size(int v){
	siz[v]=1;
	for(int u:E[v]){
		if(u!=par[v]){
			par[u]=v;
			dfs_size(u);
			siz[v]+=siz[u];
		}
	}
	for(int i=0; i<E[v].size(); i++){
		if(E[v][i]!=par[v] && siz[E[v][i]]>siz[E[v][0]])swap(E[v][i], E[v][0]);
	}
	S2.insert(siz[v]);
}
void color(int v, int c){
	if(c==0){
		S.erase(S.find(siz[v]));
		S2.insert(siz[v]);
	}
	else{
		S2.erase(S2.find(siz[v]));
		S.insert(siz[v]);
	}
	for(int u:E[v]){
		if(u!=par[v])color(u, c);
	}
}
int ans=N, n;
void solve(int v){
	for(int i=1; i<E[v].size(); i++){
		int u=E[v][i];
		if(u!=par[v]){
			solve(u);
			color(u, 0);
		}
	}
	if(E[v][0]!=par[v]){
		solve(E[v][0]);
	}
	for(int i=1; i<E[v].size(); i++){
		int u=E[v][i];
		if(u!=par[v]){
			color(u, 1);
		}
	}
	if(par[v]==0)return;
	S2.erase(S2.find(siz[v]));
	int k=siz[v]/2;
	auto it=S.upper_bound(k);
	if(it!=S.end()){
		ans=min(ans, max({siz[v]-*it, *it, n-siz[v]})-min({siz[v]-*it, *it, n-siz[v]}));
	}
	if(it!=S.begin()){
		it=prev(it);
		ans=min(ans, max({siz[v]-*it, *it, n-siz[v]})-min({siz[v]-*it, *it, n-siz[v]}));
	}
	k=(n-siz[v])/2;
	it=S2.upper_bound(k);
	if(it!=S2.end()){
		if(*it<=siz[v])ans=min(ans, max({n-siz[v]-*it, *it, siz[v]})-min({n-siz[v]-*it, *it, siz[v]}));
	}
	if(it!=S2.begin()){
		it=prev(it);
		if(*it<=siz[v])ans=min(ans, max({n-siz[v]-*it, *it, siz[v]})-min({n-siz[v]-*it, *it, siz[v]}));
	}
	S.insert(siz[v]);
	//assert(S.size()==siz[v] && S2.size()==n-siz[v]);
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1; i<n; i++){
		int u, v;
		cin>>u>>v;
		E[u].push_back(v);
		E[v].push_back(u);
	}
	dfs_size(1);
	solve(1);
	cout<<ans;
}

Compilation message (stderr)

papricice.cpp: In function 'void dfs_size(int)':
papricice.cpp:19:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i=0; i<E[v].size(); i++){
      |               ~^~~~~~~~~~~~
papricice.cpp: In function 'void solve(int)':
papricice.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i=1; i<E[v].size(); i++){
      |               ~^~~~~~~~~~~~
papricice.cpp:49:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i=1; i<E[v].size(); i++){
      |               ~^~~~~~~~~~~~

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