oj.uz

Submission #735587

# Submission time Handle Problem Language Result Execution time Memory
735587 2023-05-04T11:20:22 Z Koful123 Papričice (COCI20_papricice) C++17
110 / 110
 428 ms 29152 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

const int N = 2e5 + 5;
int ans = 1e18,n;
vector<int> adj[N],sz(N);
multiset<int> other,anc;

void calc(int node,int p){
	sz[node] = 1;
	for(int go : adj[node]){
		if(go == p) continue;
		calc(go,node);
		sz[node] = sz[go] + sz[node];
	}
}

int search(multiset<int> &s,int x,int ty){
	int res = 1e18,cur = x;
	if(!ty) cur = (n - x) / 2 + x;
	else cur = (n - x) / 2;
	auto it = s.upper_bound(cur);
	if(ty){
		if(it != s.end()){
			vector<int> tmp = {x,n - x - *it,*it};
			sort(tmp.begin(), tmp.end());
			res = min(res,tmp[2] - tmp[0]);
		}
		if(it != s.begin()){
			vector<int> tmp = {x,n - *prev(it) - x,*prev(it)};
			sort(tmp.begin(), tmp.end());
			res = min(res,tmp[2] - tmp[0]);
		}
		return res;		
	}

	if(it != s.end()){
		vector<int> tmp = {x,n - *it,*it - x};
		sort(tmp.begin(), tmp.end());
		res = min(res,tmp[2] - tmp[0]);
	}
	if(it != s.begin()){
		vector<int> tmp = {x,n - *prev(it),*prev(it) - x};
		sort(tmp.begin(), tmp.end());
		res = min(res,tmp[2] - tmp[0]);
	}
	return res;
}

void dfs(int node,int p){
	ans = min({ans,search(anc,sz[node],0),search(other,sz[node],1)});
	anc.insert(sz[node]);
	for(int go : adj[node]){
		if(go == p) continue;
		dfs(go,node);
	}
	anc.erase(anc.find(sz[node]));
	other.insert(sz[node]);
}	

void solve(){

	cin >> n;
	for(int i = 1; i < n; i++){
		int a,b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	calc(1,0);
	dfs(1,0);

	cout << ans << endl;
}
 
signed main(){ 
 
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	int t = 1;
//	cin >> t;
 
	while(t--)
		solve();
 	
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 5 ms 6496 KB Output is correct
3 Correct 5 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 4 ms 6484 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 5 ms 6496 KB Output is correct
3 Correct 5 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 4 ms 6484 KB Output is correct
6 Correct 5 ms 6740 KB Output is correct
7 Correct 5 ms 6736 KB Output is correct
8 Correct 4 ms 6740 KB Output is correct
9 Correct 5 ms 6740 KB Output is correct
10 Correct 5 ms 6740 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 5 ms 6496 KB Output is correct
3 Correct 5 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 4 ms 6484 KB Output is correct
6 Correct 5 ms 6740 KB Output is correct
7 Correct 5 ms 6736 KB Output is correct
8 Correct 4 ms 6740 KB Output is correct
9 Correct 5 ms 6740 KB Output is correct
10 Correct 5 ms 6740 KB Output is correct
11 Correct 280 ms 25824 KB Output is correct
12 Correct 300 ms 25780 KB Output is correct
13 Correct 235 ms 26348 KB Output is correct
14 Correct 247 ms 26140 KB Output is correct
15 Correct 309 ms 25764 KB Output is correct
16 Correct 238 ms 25464 KB Output is correct
17 Correct 264 ms 25804 KB Output is correct
18 Correct 277 ms 29152 KB Output is correct
19 Correct 273 ms 26088 KB Output is correct
20 Correct 428 ms 25756 KB Output is correct