Submission #472623

#	Time	Username	Problem	Language	Result	Execution time	Memory
472623		kungfulon	Papričice (COCI20_papricice)	C++17	110 / 110	391 ms	29288 KiB

papricice

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int n,ans = 1e9;
vector<int> g[200001];
int kids[200001];
multiset<int> si,so;

void DFS(int u,int p = -1){
	kids[u] = 1;
	for(auto v : g[u]) if(v != p){
		DFS(v,u);
		kids[u] += kids[v];
	}
}

inline void calc(int x,int y,int z){
	ans = min(ans,max({abs(x-y),abs(y-z),abs(x-z)}));
}

void solve(int u,int p = -1){
	/// y nam trong x 
	auto in = si.lower_bound((n - kids[u])/2);
	if(in != si.end()){
		calc(*in,n-kids[u]-(*in),kids[u]);
	}
	if(in != si.begin()){
		auto pin = prev(in);
		calc(*pin,n-kids[u]-(*pin),kids[u]);
	}
	/// y nam ngoai x
	auto out = so.lower_bound((n - kids[u])/2);
	if(out != so.end()){
		calc(*out,n-kids[u]-(*out),kids[u]);
	}
	if(out != so.begin()){
		auto pout = prev(out);
		calc(*pout,n-kids[u]-(*pout),kids[u]);
	}

	si.insert(n - kids[u]);
	for(auto v : g[u]) if(v != p){
		solve(v,u);
	}
	so.insert(kids[u]);
	si.erase(si.find(n - kids[u]));
}

int main(int argc,const char** argv){
	cin >> n;
	for(int i = 1;i < n;i++){
		int x,y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	DFS(1);
	solve(1);
	cout << ans;
}

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