oj.uz

Submission #476313

# Submission time Handle Problem Language Result Execution time Memory
476313 2021-09-26T02:25:23 Z Mackerel_Pike Papričice (COCI20_papricice) C++14
110 / 110
 300 ms 25784 KB 
#include <bits/stdc++.h>

using namespace std;

#define PB push_back
const int maxn = 2e5 + 5;

int n, ans = 0x3f3f3f3f;
int siz[maxn];
vector<int> tree[maxn];

inline void precalc(int u, int p){
  siz[u] = 1;
  for(int i = 0; i < tree[u].size(); ++i){
    int v = tree[u][i];
    if(v == p)
      continue;
    precalc(v, u);
    siz[u] += siz[v];
  }
  return;
}

inline void calc(int x, int y, int z){
  ans = min(ans, max(x, max(y, z)) - min(x, min(y, z)));
  return;
}

inline void query(multiset<int> &S, int x, int k){
  multiset<int>::iterator it = S.lower_bound(x);
  if(it != S.end())
    calc(*it, k, n - k - *it);
  if(it != S.begin())
    --it, calc(*it, k, n - k - *it);
  return;
}

multiset<int> S, T;

inline void dfs(int u, int p){
  query(S, (n - siz[u] + 1) / 2, siz[u]);
  query(T, (n - siz[u] + 1) / 2, siz[u]);
  S.insert(n - siz[u]);
  for(int i = 0; i < tree[u].size(); ++i){
    int v = tree[u][i];
    if(v == p)
      continue;
    dfs(v, u);
  }
  S.erase(S.find(n - siz[u]));
  T.insert(siz[u]);
  return;
}

int main(){
  //freopen("papricice.in", "r", stdin);
  
  scanf("%d", &n);
  for(int i = 1; i < n; ++i){
    int u, v; scanf("%d%d", &u, &v);
    --u, --v;
    tree[u].PB(v), tree[v].PB(u);
  }

  precalc(0, -1);
  dfs(0, -1);

  printf("%d\n", ans);
  return 0;
}

Compilation message

papricice.cpp: In function 'void precalc(int, int)':
papricice.cpp:14:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   for(int i = 0; i < tree[u].size(); ++i){
      |                  ~~^~~~~~~~~~~~~~~~
papricice.cpp: In function 'void dfs(int, int)':
papricice.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(int i = 0; i < tree[u].size(); ++i){
      |                  ~~^~~~~~~~~~~~~~~~
papricice.cpp: In function 'int main()':
papricice.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
papricice.cpp:60:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     int u, v; scanf("%d%d", &u, &v);
      |               ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 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 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 5 ms 5108 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 4 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 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 5 ms 5108 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 4 ms 5068 KB Output is correct
11 Correct 288 ms 21548 KB Output is correct
12 Correct 300 ms 21472 KB Output is correct
13 Correct 228 ms 22084 KB Output is correct
14 Correct 236 ms 21816 KB Output is correct
15 Correct 278 ms 21432 KB Output is correct
16 Correct 188 ms 22208 KB Output is correct
17 Correct 289 ms 21556 KB Output is correct
18 Correct 254 ms 25784 KB Output is correct
19 Correct 234 ms 21652 KB Output is correct
20 Correct 259 ms 21452 KB Output is correct