Submission #870193

#	Time	Username	Problem	Language	Result	Execution time	Memory
870193		NotLinux	Papričice (COCI20_papricice)	C++17	0 / 110	3 ms	14940 KiB

papricice

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
int n,ans = 1e9 + 7,subt[N];
vector < int > tree[N];
set < int > cont[N];
inline int eval(int a , int b , int c){
	//printf("eval(%d,%d,%d) ",a,b,c);
	return max({abs(a-b) , abs(a-c) , abs(b-c)});
}
inline int find_t1(int a1){
	return (n - a1)/2;
}
inline int find_t2(int a1){
	return (n - a1);
}
inline int closest_set(int tar , set < int > &ste){
	auto hi = ste.lower_bound(tar);
	auto lo = --ste.lower_bound(tar);
	if(hi == ste.end())return *lo;
	else if(hi == ste.begin())return *hi;
	else if(abs(tar-*hi) < abs(tar-*lo))return *hi;
        else return *lo;
}
inline int closest_vec(int tar , deque < int > &vec){
	auto hi = lower_bound(vec.begin() , vec.end() , tar);
	auto lo = --lower_bound(vec.begin() , vec.end() , tar);
	if(hi == vec.end())return *lo;
	else if(hi == vec.begin())return *hi;
	else if(abs(tar-*hi) < abs(tar-*lo))return *hi;
        else return *lo;
}
inline void dfs0(int node , int past){
	subt[node] = 1;
	for(auto itr : tree[node]){
		if(itr != past){
			dfs0(itr,node);
			subt[node] += subt[itr];
		}
	}
}
inline void dfs1(int node , int past){
	if(tree[node].size() == 1 and past != 0){//leaf ise
		cont[node].insert(1);
		return;
	}
	vector < int > cand;
	int mxnode = -1;
	for(auto itr : tree[node]){
		if(itr != past){
			dfs1(itr,node);
			cand.push_back(itr);
			if(mxnode == -1 or subt[mxnode] < subt[itr])mxnode = itr;
		}
	}
	cand.erase(find(cand.begin() , cand.end() , mxnode));
	//cout << "node : " << node << endl;
	for(auto itr : cand){
		for(auto itr1 : cont[itr]){
			int itr2 = closest_set(find_t1(itr1),cont[mxnode]);
	//		cout << "dfs1 - " << node << " " << itr1 << " " << itr2 << endl;
			ans = min(ans , eval(n-itr1-itr2,itr1,itr2));
			cont[mxnode].insert(itr1);
		}
		cont[itr].clear();
	}
	cont[node].swap(cont[mxnode]);
	cont[node].insert(subt[node]);
}
deque < int > path;
inline void dfs2(int node , int past){
	if(path.size() > 1){
		//cout << "optimal : " << find_t2(subt[node]) << endl;
		//cout << "node : ";for(auto itr : path)cout << itr << " ";cout << endl;
		int itr1 = subt[node] , itr2 = closest_vec(find_t2(subt[node]),path);
		//cout << "dfs2 : " << node << " , " << itr1 << " , " << itr2 << " = " << eval(n-itr2,itr2-itr1,itr1) << endl;
		ans = min(ans , eval(n-itr2,itr2-itr1,itr1));
	}
	for(auto itr : tree[node]){
		if(itr != past){
			path.push_front(subt[node]);
			dfs2(itr,node);
			path.pop_front();
		}
	}
}
void solve(){
	cin >> n;
	for(int i = 1;i<n;i++){
		int u,v;cin >> u >> v;
		tree[u].push_back(v);
		tree[v].push_back(u);
	}
	//precalc : subtree size
	dfs0(1,0);
	//small to large ile disjoint setlerin cevabını bul
	dfs1(1,0);
	//cout << "dfs1 : " << ans << endl;
	//bs ile iç içe setlerin cevabını bul
	dfs2(1,0);
	//cout << "dfs2 : " << ans << endl;
	cout << ans << endl;
}
signed main(){
	//ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

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