oj.uz

Submission #446269

# Submission time Handle Problem Language Result Execution time Memory
446269 2021-07-21T11:50:13 Z Antekb Papričice (COCI20_papricice) C++14
50 / 110
 1000 ms 24756 KB 
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int N=2e5+5;
multiset<int> S, S2;//S-subtree, S2=tree\subtree
int siz[N], par[N];
vector<int> E[N];
void dfs_size(int v){
	siz[v]=1;
	for(int u:E[v]){
		if(u!=par[v]){
			par[u]=v;
			dfs_size(u);
			siz[v]+=siz[u];
		}
	}
	for(int i=0; i<E[v].size(); i++){
		if(E[v][i]!=par[v] && siz[E[v][i]]>siz[E[v][0]])swap(E[v][i], E[v][0]);
	}
	S2.insert(siz[v]);
}
void color(int v, int c){
	if(c==0){
		S.erase(S.find(siz[v]));
		S2.insert(siz[v]);
	}
	else{
		S2.erase(S2.find(siz[v]));
		S.insert(siz[v]);
	}
	for(int u:E[v]){
		if(u!=par[v])color(u, c);
	}
}
int ans=N, n;
void solve(int v){
	for(int i=1; i<E[v].size(); i++){
		int u=E[v][i];
		if(u!=par[v]){
			solve(u);
			color(u, 0);
		}
	}
	if(E[v][0]!=par[v]){
		solve(E[v][0]);
	}
	for(int i=1; i<E[v].size(); i++){
		int u=E[v][i];
		if(u!=par[v]){
			color(u, 1);
		}
	}
	if(par[v]==0)return;
	S2.erase(S2.find(siz[v]));
	int k=siz[v]/2;
	auto it=S.upper_bound(k);
	if(it!=S.end()){
		ans=min(ans, max({siz[v]-*it, *it, n-siz[v]})-min({siz[v]-*it, *it, n-siz[v]}));
	}
	if(it!=S.begin()){
		it=prev(it);
		ans=min(ans, max({siz[v]-*it, *it, n-siz[v]})-min({siz[v]-*it, *it, n-siz[v]}));
	}
	k=(n-siz[v])/2;
	it=S2.upper_bound(k);
	if(it!=S2.end()){
		if(*it<=siz[v])ans=min(ans, max({n-siz[v]-*it, *it, siz[v]})-min({n-siz[v]-*it, *it, siz[v]}));
	}
	if(it!=S2.begin()){
		it=prev(it);
		if(*it<=siz[v])ans=min(ans, max({n-siz[v]-*it, *it, siz[v]})-min({n-siz[v]-*it, *it, siz[v]}));
	}
	S.insert(siz[v]);
	//assert(S.size()==siz[v] && S2.size()==n-siz[v]);
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1; i<n; i++){
		int u, v;
		cin>>u>>v;
		E[u].push_back(v);
		E[v].push_back(u);
	}
	dfs_size(1);
	solve(1);
	cout<<ans;
}

Compilation message

papricice.cpp: In function 'void dfs_size(int)':
papricice.cpp:19:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i=0; i<E[v].size(); i++){
      |               ~^~~~~~~~~~~~
papricice.cpp: In function 'void solve(int)':
papricice.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i=1; i<E[v].size(); i++){
      |               ~^~~~~~~~~~~~
papricice.cpp:49:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i=1; i<E[v].size(); i++){
      |               ~^~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5020 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 3 ms 5024 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 7 ms 5196 KB Output is correct
7 Correct 7 ms 5196 KB Output is correct
8 Correct 6 ms 5160 KB Output is correct
9 Correct 6 ms 5196 KB Output is correct
10 Correct 7 ms 5216 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5020 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 3 ms 5024 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 7 ms 5196 KB Output is correct
7 Correct 7 ms 5196 KB Output is correct
8 Correct 6 ms 5160 KB Output is correct
9 Correct 6 ms 5196 KB Output is correct
10 Correct 7 ms 5216 KB Output is correct
11 Execution timed out 1076 ms 24756 KB Time limit exceeded
12 Halted 0 ms 0 KB -