oj.uz

Submission #479411

# Submission time Handle Problem Language Result Execution time Memory
479411 2021-10-11T15:51:13 Z Neos Papričice (COCI20_papricice) C++14
110 / 110
 239 ms 28404 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 4968 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 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 4968 KB Output is correct
6 Correct 6 ms 5068 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 5 ms 5068 KB Output is correct
10 Correct 5 ms 5068 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 4 ms 4968 KB Output is correct
6 Correct 6 ms 5068 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 5 ms 5068 KB Output is correct
10 Correct 5 ms 5068 KB Output is correct
11 Correct 207 ms 12228 KB Output is correct
12 Correct 228 ms 14700 KB Output is correct
13 Correct 201 ms 15056 KB Output is correct
14 Correct 185 ms 14856 KB Output is correct
15 Correct 220 ms 14608 KB Output is correct
16 Correct 180 ms 14528 KB Output is correct
17 Correct 198 ms 14816 KB Output is correct
18 Correct 239 ms 28404 KB Output is correct
19 Correct 189 ms 14736 KB Output is correct
20 Correct 219 ms 14852 KB Output is correct