oj.uz

Submission #479405

# Submission time Handle Problem Language Result Execution time Memory
479405 2021-10-11T15:44:50 Z Neos Papričice (COCI20_papricice) C++14
50 / 110
 1000 ms 14888 KB 
#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;
  for (auto it: find(A, (n + f[u]) / 2))
    ans = min(ans, get(f[u], it, n));
  for (auto it: find(B, (n - f[u]) / 2))
    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 3 ms 4940 KB Output is correct
4 Correct 3 ms 5020 KB Output is correct
5 Correct 3 ms 4940 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 3 ms 4940 KB Output is correct
4 Correct 3 ms 5020 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 7 ms 5068 KB Output is correct
7 Correct 15 ms 5136 KB Output is correct
8 Correct 6 ms 5064 KB Output is correct
9 Correct 8 ms 5068 KB Output is correct
10 Correct 13 ms 5068 KB Output is correct

Subtask #3
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 3 ms 4940 KB Output is correct
4 Correct 3 ms 5020 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 7 ms 5068 KB Output is correct
7 Correct 15 ms 5136 KB Output is correct
8 Correct 6 ms 5064 KB Output is correct
9 Correct 8 ms 5068 KB Output is correct
10 Correct 13 ms 5068 KB Output is correct
11 Execution timed out 1088 ms 14888 KB Time limit exceeded
12 Halted 0 ms 0 KB -