oj.uz

답안 #484531

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
484531 2021-11-04T06:37:32 Z Nimbostratus Papričice (COCI20_papricice) C++17
0 / 110
 4 ms 5068 KB 
#include "bits/stdc++.h"
#define endl '\n'
#define fi first
#define se second
constexpr int maxn = 2e5+5;
constexpr int inf = 1e9;
constexpr int mod = 1e9+7;
using namespace std;
using lint = long long;
using pii = pair<int,int>;

int n, ans;
vector<int> adj[maxn];
int sub[maxn];
map<int, int> a, b;

void calcsub(int u) {
	sub[u] = 1;
	for(int v : adj[u]) {
		if(sub[v])
			continue;
		calcsub(v);
		sub[u] += sub[v];
	}
}

void calcans(int u) {
	map<int, int>::iterator it;
	int mx, mn;
	it = a.lower_bound((n + sub[u] + 1) / 2);
	if(it != a.end()) {
		int x = it->fi;
		mx = max({sub[u], x - sub[u], n - x});
		mn = min({sub[u], x - sub[u], n - x});
		ans = min(ans, mx - mn);
	}
	if(it != a.begin()) {
		it--;
		int x = it->fi;
		mx = max({sub[u], x - sub[u], n - x});
		mn = min({sub[u], x - sub[u], n - x});
		ans = min(ans, mx - mn);
	}
	it = b.lower_bound((n - sub[u] + 1) / 2);
	if(it != b.end()) {
		int x = it->fi;
		mx = max({sub[u], x, n - sub[u] - x});
		mn = min({sub[u], x, n - sub[u] - x});
		ans = min(ans, mx - mn);
	}
	if(it != b.begin()) {
		it--;
		int x = it->fi;
		mx = max({sub[u], x, n - sub[u] - x});
		mn = min({sub[u], x, n - sub[u] - x});
		ans = min(ans, mx - mn);
	}
}

void dfs(int u) {
	calcans(u);
	a[sub[u]]++;
	for(int v : adj[u]) {
		if(a[sub[v]])
			continue;
		dfs(v);
	}
	a[sub[u]]--;
	if(!a[sub[u]])
		a.erase(sub[u]);
	b[sub[u]]++;
}

signed main() {
	#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	#endif
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for(int i = 1, x, y; i < n; i++) {
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	ans = inf;
	calcsub(1);
	dfs(1);
	cout << ans << endl;
}

Compilation message

papricice.cpp: In function 'int main()':
papricice.cpp:76:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  freopen("in.txt","r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~
papricice.cpp:77:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |  freopen("out.txt","w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 5068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 5068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 5068 KB Output isn't correct
2 Halted 0 ms 0 KB -