Submission #1272237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272237		nhq0914	Papričice (COCI20_papricice)	C++17	110 / 110	132 ms	19272 KiB

papricice

#include <bits/stdc++.h>
#define vi vector <int>
using namespace std;
const int N = 2e5 + 1;
int n;
int sz[N];
int ans = 2e9;
set <int> undone, done;
vi g[N];
void predfs(int v, int par = 0){
	sz[v] = 1;
	for(int &x: g[v]) if(x != par){
		predfs(x, v);
		sz[v] += sz[x];
	}
}
int cmp(int x, int a){
	int b = n - x - a;
	if(a < b) a ^= b ^= a ^= b;
	if(x > a) return x - b;
	if(x < b) return a - x;
	return a - b;
}
void dfs(int v, int par = 0){
	auto it = done.lower_bound((n - sz[v]) / 2);
	if(it != done.end())
		ans = min(ans, cmp(sz[v], *it));
	if(it != done.begin())
		ans = min(ans, cmp(sz[v], *prev(it)));
	it = undone.lower_bound((n - sz[v]) / 2 + sz[v]);
	if(it != undone.end())
		ans = min(ans, cmp(sz[v], *it - sz[v]));
	if(it != undone.begin())
		ans = min(ans, cmp(sz[v], *prev(it) - sz[v]));
	undone.insert(sz[v]);
	for(int &x: g[v]) if(x != par){
		dfs(x, v);
	}
	undone.erase(sz[v]);
	done.insert(sz[v]);
}
int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);
	cin >> n;
	for(int u, v, i = 1; i < n; ++i){
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	predfs(1);
	dfs(1);
	cout << ans;
	cerr << "ok\n";
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 60 / 60