Submission #476313

#	Time	Username	Problem	Language	Result	Execution time	Memory
476313		Mackerel_Pike	Papričice (COCI20_papricice)	C++14	110 / 110	300 ms	25784 KiB

papricice

#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 (stderr)

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 / 15
• Subtask 2: 35 / 35
• Subtask 3: 60 / 60