Submission #851407

#	Time	Username	Problem	Language	Result	Execution time	Memory
851407		vjudge1	Papričice (COCI20_papricice)	C++98	50 / 110	1039 ms	47696 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 = 2e5+1;

vi sz(N),best(N),edges[N],tin(N),tout(N);
set<int> sts[N];
int timer = 1;
int getsz(int node,int parent) {
	tin[node] = timer++;
	int ans = 1;
	for (auto nb : edges[node]) {
		if (nb != parent) ans+=getsz(nb,node);
	}
	tout[node] = timer++;
	return sz[node] = ans;
}
bool is_anc(int a,int b) {return tin[a] <= tin[b] && tout[a] >= tout[b];}
void setswap(int node,int parent) {
	double targ = sz[node]/2.0;
	double c = abs(targ-sz[node]);
	int d = sz[node];
	sts[node].insert(sz[node]);
	for (auto nb : edges[node]) {
		if (nb==parent) continue;
		setswap(nb,node);
		if (nb != parent) {
			if (sts[nb].size() > sts[node].size()) swap(sts[nb],sts[node]);
			for (auto it : sts[nb]) sts[node].insert(it);
		}
	}
	for (auto it : sts[node]) {
		if (abs(targ-it) < c) {
			c = abs(targ-it);
			d = it;
		}
	}
	best[node] = d;
}


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);
	}
	getsz(1,1);
	setswap(1,1);
	int ans = 1e18;
	for (int i=2;i<=n;i++) {
		if (sz[i] == 1) continue;
		int haha1 = n-sz[i];
		int haha2 = sz[i]-best[i];
		int haha3 = best[i];
		int v = max({haha1,haha2,haha3})-min({haha1,haha2,haha3});
		ans = min(ans,v);
	}
	for (int i=1;i<=n;i++) {
		for (int j=i+1;j<=n;j++) {
			if (is_anc(i,j)) continue;
			int haha1 = sz[i];
			int haha2 = sz[j];
			int haha3 = n-sz[i]-sz[j];
			ans = min(ans,max({haha1,haha2,haha3})-min({haha1,haha2,haha3}));
		}
	}
	cout << ans << 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: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 0 / 60