Submission #851584

#	Time	Username	Problem	Language	Result	Execution time	Memory
851584		vjudge1	Papričice (COCI20_papricice)	C++98	0 / 110	15 ms	59996 KiB

papricice

#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
#define int long long
#define vi vector<int>
#define pb push_back
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
const int N = 4e5+1;
const int inf = 1e18;
vi sz(N),best(N),edges[N],tin(N),tout(N),tour = {0};
vi t[4*N];
int timer = 1;

int dfs(int node,int parent) {
	tour.pb(node);
	tin[node] = timer++;
	int ans = 1;
	for (auto nb : edges[node]) {
		if (nb != parent) ans+=dfs(nb,node);
	}
	tout[node] = timer++;
	tour.pb(node);
	return sz[node] = ans;
}


vi merge(vi&a ,vi& b) {
	int ptr = 0,ptr2 = 0;
	vi v;
	int n = a.size();
	int m = b.size();
	while (ptr < n && ptr2 < m) {
		if (a[ptr] < b[ptr2]) v.pb(a[ptr++]);
		else v.pb(b[ptr2++]);
	}
	while (ptr < n) v.pb(a[ptr++]);
	while (ptr2 < m) v.pb(b[ptr2++]);
	return v;
}

void build(int node,int l,int r) {
	if (l == r) {
		t[node].pb(sz[tour[l]]);
		return;
	}
	int m = (l+r) >> 1;
	build(2*node,l,m);
	build(2*node+1,m+1,r);
	t[node] = merge(t[2*node],t[2*node+1]);
}

pair<int,int> query(int node,int l,int r,int L,int R,double x) {
	if (l > R || r < L) return {inf,-inf};
	if (l >= L && r <= R){
		int x1=inf,x2=inf;
		auto it = lower_bound(t[node].begin(),t[node].end(),x);
		if(it!=t[node].end()) x2 =*it;
		if (it != t[node].begin()) x1 = *prev(it);
		if (abs(x-x1) < abs(x-x2)) return {abs(x-x1),x1};
		else return {abs(x-x2),x2};
	}
	int m = (l+r) >> 1;
	return min(query(2*node,l,m,L,R,x),query(2*node+1,m+1,r,L,R,x));
}


void solve() {
	int n;
	cin >> n;
	for (int i=1;i<=n-1;i++) {
		int a,b;
		cin >> a >> b;
		edges[a].pb(b);
		edges[b].pb(a);
	}
	dfs(1,1);
	int m = tour.size()-1;
	build(1,1,m);
	int best = inf;
	for (int i=1;i<=n;i++) {
		//cout << "Node" sp i sp ":";
		int l = tin[i];
		int r = tout[i];
		pair<int,int> h = min(query(1,1,n,1,l-1,(n-sz[i])/2.0),
							   query(1,1,n,r+1,m,(n-sz[i])/2.0));
		int h1 = h.second; 
		int h2 = n-sz[i]-h1;
		int h3 = sz[i];
		int v =max({h1,h2,h3})-min({h1,h2,h3});
		//cout << v << " ";
		h = query(1,1,n,l+1,r-1,(sz[i]/2.0));
		h1 = h.second;
		h2 = sz[i]-h1;
		h3 = n-sz[i];
		v = max({h1,h2,h3})-min({h1,h2,h3});
		//cout << v << endl;
		best = min(best,v);
	} 
	cout << best << endl;
}    
 
 
 
                                
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}
 
 
 

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