oj.uz

Submission #399257

# Submission time Handle Problem Language Result Execution time Memory
399257 2021-05-05T13:37:52 Z retsiger Papričice (COCI20_papricice) C++14
110 / 110
 225 ms 21584 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4932 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 4 ms 4948 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4932 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 4 ms 4948 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 4 ms 5044 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 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4932 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 4 ms 4948 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 4 ms 5044 KB Output is correct
10 Correct 5 ms 5068 KB Output is correct
11 Correct 217 ms 14696 KB Output is correct
12 Correct 225 ms 14632 KB Output is correct
13 Correct 194 ms 15356 KB Output is correct
14 Correct 178 ms 14788 KB Output is correct
15 Correct 208 ms 14580 KB Output is correct
16 Correct 129 ms 14604 KB Output is correct
17 Correct 203 ms 14816 KB Output is correct
18 Correct 218 ms 21584 KB Output is correct
19 Correct 191 ms 14824 KB Output is correct
20 Correct 204 ms 14796 KB Output is correct