oj.uz

Submission #851394

# Submission time Handle Problem Language Result Execution time Memory
851394 2023-09-19T17:26:44 Z vjudge1 Papričice (COCI20_papricice) C++
0 / 110
 6 ms 17500 KB 
#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];
set<int> sts[N];

int getsz(int node,int parent) {
	int ans = 1;
	for (auto nb : edges[node]) {
		if (nb != parent) ans+=getsz(nb,node);
	}
	return sz[node] = ans;
}

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);
	//for (int i=1;i<=n;i++) cout << best[i] << " ";
	//cout << endl;
	int ans = 1e18;
	for (int i=1;i<=n;i++) {
		int haha1 = n-sz[i];
		int haha2 = sz[i]-best[i];
		int haha3 = best[i];
		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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17496 KB Output is correct
2 Correct 5 ms 17500 KB Output is correct
3 Incorrect 6 ms 17500 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17496 KB Output is correct
2 Correct 5 ms 17500 KB Output is correct
3 Incorrect 6 ms 17500 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 17496 KB Output is correct
2 Correct 5 ms 17500 KB Output is correct
3 Incorrect 6 ms 17500 KB Output isn't correct
4 Halted 0 ms 0 KB -