oj.uz

Submission #476306

# Submission time Handle Problem Language Result Execution time Memory
476306 2021-09-26T01:46:48 Z Mackerel_Pike Papričice (COCI20_papricice) C++14
15 / 110
 4 ms 5068 KB 
#include <bits/stdc++.h>

using namespace std;

#define MP make_pair
#define PB push_back
#define fst first
#define snd second

const int maxn = 2e5 + 5;

int n;
int siz[maxn], mx[maxn];
vector<int> tree[maxn], S, T;

inline void findCentroid(int u, int p, int &c){
  siz[u] = 1;
  for(int i = 0; i < tree[u].size(); ++i){
    int v = tree[u][i];
    if(v == p)
      continue;
    findCentroid(v, u, c);
    siz[u] += siz[v];
    mx[u] = max(mx[u], siz[v]);
  }
  mx[u] = max(mx[u], n - siz[u]);
  if(!~c || mx[u] < mx[c])
    c = u;
  return;
} 

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

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

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);
  }

  int c = -1; findCentroid(0, -1, c);
  vector<pair<int, int> > vec;
  for(int i = 0; i < tree[c].size(); ++i)
    if(siz[tree[c][i]] < siz[c])
      vec.PB(MP(siz[tree[c][i]], tree[c][i]));
    else
      vec.PB(MP(n - siz[c], tree[c][i]));

  sort(vec.begin(), vec.end());
  int p = vec[vec.size() - 1].snd, q = vec[vec.size() - 2].snd;
  dfs(p, c, S), dfs(q, c, T);

  sort(S.begin(), S.end());
  sort(T.begin(), T.end());

  int ans = 0x3f3f3f3f;
  
  for(int i = 0; i < S.size(); ++i){
    int pos = lower_bound(T.begin(), T.end(), (n - S[i] + 1) / 2) - T.begin();
    if(pos < T.size())
      ans = min(ans, calc(S[i], T[pos], n - S[i] - T[pos]));
    if(pos - 1 >= 0)
      ans = min(ans, calc(S[i], T[pos - 1], n - S[i] - T[pos - 1]));
  }

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

Compilation message

papricice.cpp: In function 'void findCentroid(int, int, int&)':
papricice.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   for(int i = 0; i < tree[u].size(); ++i){
      |                  ~~^~~~~~~~~~~~~~~~
papricice.cpp: In function 'void dfs(int, int, std::vector<int>&)':
papricice.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int i = 0; i < tree[u].size(); ++i){
      |                  ~~^~~~~~~~~~~~~~~~
papricice.cpp: In function 'int main()':
papricice.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for(int i = 0; i < tree[c].size(); ++i)
      |                  ~~^~~~~~~~~~~~~~~~
papricice.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for(int i = 0; i < S.size(); ++i){
      |                  ~~^~~~~~~~~~
papricice.cpp:78:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     if(pos < T.size())
      |        ~~~~^~~~~~~~~~
papricice.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
papricice.cpp:54:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     int u, v; scanf("%d%d", &u, &v);
      |               ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 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
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 Incorrect 4 ms 5068 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 Incorrect 4 ms 5068 KB Output isn't correct
7 Halted 0 ms 0 KB -