Submission #870218

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
870218	2023-11-07T08:52:38 Z	NotLinux	Papričice (COCI20_papricice)	C++17	110 / 110	239 ms	29268 KB

papricice

#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]){
		if(itr != past){
			path.insert(subt[itr]);
			dfs1(itr,node);
			path.erase(path.find(subt[itr]));
			notpath.insert(subt[itr]);
		}
	}
}
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

35.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	5220 KB	Output is correct
7	Correct	2 ms	5280 KB	Output is correct
8	Correct	2 ms	5212 KB	Output is correct
9	Correct	3 ms	5212 KB	Output is correct
10	Correct	2 ms	5328 KB	Output is correct

Subtask #3

60.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	5220 KB	Output is correct
7	Correct	2 ms	5280 KB	Output is correct
8	Correct	2 ms	5212 KB	Output is correct
9	Correct	3 ms	5212 KB	Output is correct
10	Correct	2 ms	5328 KB	Output is correct
11	Correct	174 ms	23504 KB	Output is correct
12	Correct	239 ms	23288 KB	Output is correct
13	Correct	164 ms	24288 KB	Output is correct
14	Correct	146 ms	23756 KB	Output is correct
15	Correct	220 ms	23264 KB	Output is correct
16	Correct	143 ms	23844 KB	Output is correct
17	Correct	176 ms	23560 KB	Output is correct
18	Correct	174 ms	29268 KB	Output is correct
19	Correct	219 ms	23800 KB	Output is correct
20	Correct	171 ms	23556 KB	Output is correct