oj.uz

Submission #851407

# Submission time Handle Problem Language Result Execution time Memory
851407 2023-09-19T17:44:05 Z vjudge1 Papričice (COCI20_papricice) C++
50 / 110
 1000 ms 47696 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],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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 20824 KB Output is correct
2 Correct 7 ms 20828 KB Output is correct
3 Correct 6 ms 20824 KB Output is correct
4 Correct 6 ms 20824 KB Output is correct
5 Correct 7 ms 20824 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 20824 KB Output is correct
2 Correct 7 ms 20828 KB Output is correct
3 Correct 6 ms 20824 KB Output is correct
4 Correct 6 ms 20824 KB Output is correct
5 Correct 7 ms 20824 KB Output is correct
6 Correct 16 ms 21072 KB Output is correct
7 Correct 15 ms 21080 KB Output is correct
8 Correct 14 ms 20828 KB Output is correct
9 Correct 14 ms 20824 KB Output is correct
10 Correct 18 ms 21088 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 20824 KB Output is correct
2 Correct 7 ms 20828 KB Output is correct
3 Correct 6 ms 20824 KB Output is correct
4 Correct 6 ms 20824 KB Output is correct
5 Correct 7 ms 20824 KB Output is correct
6 Correct 16 ms 21072 KB Output is correct
7 Correct 15 ms 21080 KB Output is correct
8 Correct 14 ms 20828 KB Output is correct
9 Correct 14 ms 20824 KB Output is correct
10 Correct 18 ms 21088 KB Output is correct
11 Execution timed out 1039 ms 47696 KB Time limit exceeded
12 Halted 0 ms 0 KB -