Submission #479411

#	Time	Username	Problem	Language	Result	Execution time	Memory
479411		Neos	Papričice (COCI20_papricice)	C++14	110 / 110	239 ms	28404 KiB

papricice

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vii> vvii;
 
#define task "test"
#define fastIO ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define forw(i, l, r) for( ll i = (l) ; i < (r) ; i++ )
#define forb(i, r, l) for( ll i = (r) ; i >= (l) ; i-- )
#define numBit(x) (__builtin_popcountll(1ll * (x)))
#define getBit(x, i) ((x) >> (i) & 1)
#define sz(x) (int)x.size()
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define debug(x) cerr << #x << " = " << x << '\n';
 
const int N = 2e5 + 7;
const ll inf = 0x3f3f3f3f;

int n, f[N];
set<int> A, B;
vi adj[N];

void dfs(int u, int p = -1) {
  f[u] = 1;
  for (int v: adj[u]) if (v != p) {
    dfs(v, u);
    f[u] += f[v];
  }
}

vi find(set<int> &s, int v) {
  vi ret;

  auto it = s.lower_bound(v);
  if (it != s.end()) ret.pb(*it);
  if (it != s.begin()) {
    --it;
    ret.pb(*it);
  }
  return ret;
}

int get(int x, int y, int z) {
  return max(x, max(y - x, z - y)) - min(x, min(y - x, z - y));
}

int get2(int x, int y, int z) {
  return max(x, max(y, z - y - x)) - min(x, min(y, z - y - x));
}

int solve(int u, int p) {
  int ans = inf;
  vi x = find(A, (n + f[u]) / 2), y = find(B, (n - f[u]) / 2);
  for (auto it: x)
    ans = min(ans, get(f[u], it, n));
  for (auto it: y)
    ans = min(ans, get2(f[u], it, n));

  A.insert(f[u]);
  for (int v: adj[u]) if (v != p) 
    ans = min(ans, solve(v, u));

  A.erase(f[u]), B.insert(f[u]);
  return ans;
}

int main() {
  fastIO;

  cin >> n;
  forw(i, 0, n - 1) {
    int u, v; cin >> u >> v;
    adj[u].pb(v); 
    adj[v].pb(u);
  }

  dfs(1);
  cout << solve(1, -1) << endl;
}

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