oj.uz

Submission #472436

# Submission time Handle Problem Language Result Execution time Memory
472436 2021-09-13T14:40:22 Z mychecksedad Papričice (COCI20_papricice) C++17
110 / 110
 306 ms 29292 KB 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
int n, ans = 3700000, a, b;
vector<vector<int>> g;
vector<int> dp;
multiset<int> s;
void dfs(int v, int p){
	dp[v] = 1;
	for(int u: g[v])
		if(u != p) dfs(u, v), dp[v] += dp[u];
}
void dfs1(int v, int p){
	auto it = s.lower_bound((n-dp[v]) / 2);
	if(it == s.begin()){
		if(it != s.end()){
			int x = *it, y = n-(dp[v]+x);
			ans = min(ans, max({abs(x - dp[v]), abs(x - y), abs(y - dp[v])}));
		}
	}else{
		if(it != s.end()){
			int x = *it, y = n-(dp[v]+x);
			ans = min(ans, max({abs(x - dp[v]), abs(x - y), abs(y - dp[v])}));
		}
		--it;
		int x = *it, y = n-(dp[v]+x);
		ans = min(ans, max({abs(x - dp[v]), abs(x - y), abs(y - dp[v])}));
	}
	for(int u: g[v]) if(u != p) dfs1(u, v);
	s.insert(dp[v]);
}
void dfs2(int v, int p){
	auto it = s.lower_bound((n-dp[v]) / 2);
	if(it == s.begin()){
		if(it != s.end()){
			int x = *it, y = n-(dp[v]+x);
			ans = min(ans, max({abs(x - dp[v]), abs(x - y), abs(y - dp[v])}));
		}
	}else{
		if(it != s.end()){
			int x = *it, y = n-(dp[v]+x);
			ans = min(ans, max({abs(x - dp[v]), abs(x - y), abs(y - dp[v])}));
		}
		--it;
		int x = *it, y = n-(dp[v]+x);
		ans = min(ans, max({abs(x - dp[v]), abs(x - y), abs(y - dp[v])}));
	}
	s.insert(n - dp[v]);
	for(int u: g[v]) if(u != p) dfs2(u, v);
	s.erase(s.find(n-dp[v]));
}
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	cin >> n;
	g.resize(n+1);
	dp.resize(n+1);
	for(int i=0; i < n-1; i++){
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	dfs(1, 0);
	dfs1(1, 0);
	s.clear();
	dfs2(1, 0);
	cout << ans;


	return 0;
}

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 281 ms 24156 KB Output is correct
12 Correct 302 ms 24004 KB Output is correct
13 Correct 246 ms 24372 KB Output is correct
14 Correct 261 ms 24132 KB Output is correct
15 Correct 288 ms 23968 KB Output is correct
16 Correct 200 ms 24000 KB Output is correct
17 Correct 287 ms 24184 KB Output is correct
18 Correct 269 ms 29292 KB Output is correct
19 Correct 274 ms 24264 KB Output is correct
20 Correct 306 ms 24024 KB Output is correct