oj.uz

Submission #870215

# Submission time Handle Problem Language Result Execution time Memory
870215 2023-11-07T08:50:56 Z NotLinux Papričice (COCI20_papricice) C++17
15 / 110
 3 ms 5212 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 7;
int n,ans = 1e18 + 7,subt[N];
vector < int > tree[N];
multiset < int > path , notpath;
inline int eval(int a , int b , int c){
	return max({abs(a-b) , abs(a-c) , abs(b-c)});
}
inline vector < int > closest_set(int tar , multiset < int > &ste){
	vector < int > ret;
	auto hi = ste.lower_bound(tar);
	auto lo = --ste.lower_bound(tar);
	if(hi != ste.end())ret.push_back(*hi);
	if(hi != ste.begin())ret.push_back(*lo);
	return ret;
}
inline void dfs0(int node , int past){
	subt[node] = 1;
	for(auto itr : tree[node]){
		if(itr != past){
			dfs0(itr,node);
			subt[node] += subt[itr];
		}
	}
}
inline void dfs1(int node , int past){
	if(path.size()){
		for(auto cand : closest_set((n+subt[node])/2 , path)){
			ans = min(ans , eval(n-cand,cand-subt[node],subt[node]));
		}
	}
	if(notpath.size()){
		for(auto cand : closest_set((n-subt[node])/2 , notpath)){
			ans = min(ans , eval(n-cand-subt[node],cand,subt[node]));
		}
	}
	for(auto itr : tree[node]){
		path.insert(subt[node]);
		if(itr != past){
			dfs1(itr,node);
		}
		path.erase(path.find(subt[node]));
		notpath.insert(subt[node]);
	}
}
void solve(){
	cin >> n;
	for(int i = 1;i<n;i++){
		int u,v;cin >> u >> v;
		tree[u].push_back(v);
		tree[v].push_back(u);
	}
	//precalc : subtree size
	dfs0(1,0);
	path.insert(subt[1]);
	dfs1(1,0);
	cout << ans << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

Subtask #1
15.0 / 15.0

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

Subtask #2
0 / 35.0

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

Subtask #3
0 / 60.0

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