Submission #1165333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165333		kerem	Papričice (COCI20_papricice)	C++20	110 / 110	133 ms	25760 KiB

papricice

#include <bits/stdc++.h>
using namespace std;
//~ #define int long long
#define ll long long
#define fr first
#define sc second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e9
#define N 200000
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tuple<int,int,int> tiii;
typedef pair<int,int> pii;

int n,ans=inf;
multiset<int> s1,s2;
vector<int> d(N+5,1),g[N+5];

int ff(int a,int b,int c){
	return max(a,max(b,c))-min(a,min(b,c));
}
int dffs(int x,int ata){
	for(auto i:g[x])
		if(i!=ata)
			d[x]+=dffs(i,x);
	return d[x];
}
void dfs(int x,int ata){
	if(!s1.empty()){
		auto it=s1.lower_bound((n+d[x])/2);
		if(it!=s1.end())
			ans=min(ans,ff(d[x],*it-d[x],n-*it));
		if(it!=s1.begin()){
			it--;
			ans=min(ans,ff(d[x],*it-d[x],n-*it));
		}
	}
	if(!s2.empty()){
		auto it=s2.lower_bound((n-d[x])/2);
		if(it!=s2.end())
			ans=min(ans,ff(d[x],*it,n-d[x]-*it));
		if(it!=s2.begin()){
			it--;
			ans=min(ans,ff(d[x],*it,n-d[x]-*it));
		}
	}
	s1.insert(d[x]);
	for(auto i:g[x])
		if(i!=ata)
			dfs(i,x);
	s1.erase(s1.find(d[x]));
	s2.insert(d[x]);
}
void solve(){
	cin >> n;
	for(int i=1;i<n;i++){
		int x,y;
		cin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
	dffs(1,0);
	dfs(1,0);
	cout << ans << endl;
}
int32_t main(){
	//~ freopen("a.txt","r",stdin);
	//~ freopen("a.txt","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

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