Submission #1114275

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114275		ljtunas	Paprike (COI18_paprike)	C++14	0 / 100	922 ms	1048576 KiB

paprike

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define fi first
#define se second
#define Rep(i, n)  for(int i = 1; i <= n; ++i)
#define For(i, a, b) for(int i = a; i <= b; ++i)
#define Ford(i, a, b) for(int i = a; i >= b; --i)
#define Forv(v, h) for(auto &v : h)
#define Bit(x, i) ((x) >> (i) & 1ll)
#define onbit(x, i) ((x) | (1ll << i))
#define offbit(x, i) ((x) &~ (1ll << i))
#define cnt_bit(x) __builtin_popcountll(x)
#define Log2(x) (63 - __builtin_clzll(x))
#define all(h) h.begin(), h.end()
#define reset(h, v) (memset(h, v, sizeof(h)))
#define memoryof(v) (sizeof(v) / 1024 / 1024)

using ii  = pair<int, int>;
using ull = unsigned long long;
using db  = long double;
using vi  = vector<int>;
using vvi  = vector<vi>;
using vii  = vector<ii>;

const int dx[] = {0, 0, +1, -1};
const int dy[] = {-1, +1, 0, 0};
const int MAXN = 2e5  + 10;
const int  MOD = 1e9  + 7;
const int   oo = 1e18 + 1;
const int base = 311;

template <class X, class Y> bool maximize(X &a, const Y &b) {
    if(a < b) return a = b, true;
    return false;
}

template <class X, class Y> bool minimize(X &a, const Y &b) {
    if(a > b) return a = b, true;
    return false;
}

// (x, y) -> (u, v) = Ckn(u - x, x + y - u - v);
// Ckn(k, a) * Ckn(k, b) = C(a, a + b);  (k : 1 -> min(a, b))

void fixmod(int &val) {
    if (val < 0) val += MOD*MOD;
    val %= MOD;
}

int n, x[MAXN], y[MAXN], ans = +oo, sz[MAXN];
vi g[MAXN];

void dfs_init(int u, int par) {
	sz[u] = 1;
	Forv(v, g[u]) {
		if (v == par) continue;
		dfs_init(v, u);
		sz[u] += sz[v];
	}
}

set<int> A, B;

int calc(int a, int b, int c) {
	return max({a, b, c}) - min({a, b, c});
}

ii get(const set<int> &s, int val) {
	auto it = s.lower_bound(val);
	ii res = {-oo,-oo};
	if (it != s.end()) res.fi = *it;
	if (it != s.begin()) {
		--it;
		res.se = *it;
	}
	return res;
}

void solve(int u, int par) {
	ii res_a = get(A,(n+sz[u])/2);
	minimize(ans, calc(sz[u], res_a.fi - sz[u], n - res_a.fi));
	minimize(ans, calc(sz[u], res_a.se - sz[u], n - res_a.se));

	ii res_b = get(B, (n-sz[u])/2);
	minimize(ans, calc(sz[u], res_b.fi, n-res_b.fi-sz[u]));
	minimize(ans, calc(sz[u], res_b.se, n-res_b.se-sz[u]));
	A.insert(sz[u]);
	Forv(v, g[u]) {
		if (v != par) solve(v, u);
	}
	A.erase(sz[u]);
	B.insert(sz[u]);
}

void Progess() {
	cin >> n;
	For(i, 1, n - 1) {
		cin >> x[i] >> y[i];
		g[x[i]].push_back(y[i]);
		g[y[i]].push_back(x[i]);
	}
	dfs_init(1, 0);
	solve(1, 0);
	cout << ans << '\n';
}

signed main(void) {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    cout.tie(nullptr);

    #define task "main"
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }//_______________________________
    Progess();
    cerr << "\nTime elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.\n";
    return (0 ^ 0);
}

Compilation message (stderr)

paprike.cpp: In function 'int main()':
paprike.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
paprike.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 13
• Subtask 3: 0 / 27
• Subtask 4: 0 / 49