Submission #399257

#	Time	Username	Problem	Language	Result	Execution time	Memory
399257		retsiger	Papričice (COCI20_papricice)	C++14	110 / 110	225 ms	21584 KiB

papricice

#include<bits/stdc++.h>
#define bug(x) cerr<<#x<<" = "<<x<<'\n'

using namespace std;

const int maxn = 200100, INF = 1e9;

int N, ch[maxn], ans;
vector <int> G[maxn];
set <int> A, B;

void check(int a, int b, int c) {
  int x = max({a, b, c});
  int y = min({a, b, c});
  ans = min(ans, x - y);
}

void prep(int u, int p = -1) {
  ch[u] = 1;
  for (int v : G[u]) if (v != p) {
    prep(v, u);
    ch[u] += ch[v];
  }
}

void dfs(int u, int p = -1) {
  auto it = A.lower_bound((N + ch[u]) / 2);
  check(ch[u], *it - ch[u], N - *it);
  if (it != A.begin()) {
    --it;
    check(ch[u], *it - ch[u], N - *it);
  }

  auto ti = B.lower_bound((N - ch[u]) / 2);
  check(ch[u], *ti, N - ch[u] - *ti);
  if (ti != B.begin()) {
    --ti;
    check(ch[u], *ti, N - ch[u] - *ti);
  }

  A.insert(ch[u]);
  for (int v : G[u]) if (v != p) {
    dfs(v, u);
  }
  A.erase(ch[u]);
  B.insert(ch[u]);
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
//  freopen("cc.inp", "r", stdin);
//  freopen("cc.out", "w", stdout);
  cin >> N;
  for (int u, v, i = 1; i < N; ++i) {
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  ans = INF;
  prep(1);
  dfs(1);
  cout << ans << '\n';
}

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