oj.uz

Submission #1074632

# Submission time Handle Problem Language Result Execution time Memory
1074632 2024-08-25T11:33:18 Z fryingduc Papričice (COCI20_papricice) C++17
110 / 110
 132 ms 29268 KB 
#include "bits/stdc++.h"
using namespace std;

const int maxn = 2e5 + 5;
int n;
int sz[maxn];
vector<int> g[maxn];
int ans;

void pre_dfs(int u, int prev) {
  sz[u] = 1;
  for(auto v:g[u]) {
    if(v == prev) continue;
    pre_dfs(v, u);
    sz[u] += sz[v];
  }
}
multiset<int> a, b;
int calc(int a, int b, int c) {
  return max({a, b, c}) - min({a, b, c});
}
void dfs(int u, int prev) {
  for(auto v:g[u]) {
    if(v == prev) continue;
    
    a.insert(sz[u]);
    
    auto it = a.lower_bound((n + sz[v]) / 2);
    if(it != a.end()) {
      int y = *it;
      ans = min(ans, calc(sz[v], y - sz[v], n - y));
//      cerr << "a " << v << " " << sz[v] << " " << y << " " << ans << endl;
    }
    if(it != a.begin()) {
      --it;
      int y = *it;
      ans = min(ans, calc(sz[v], y - sz[v], n - y));
//      cerr << "a " << v << " " << sz[v] << " " << y << " " << ans << endl;
    }
    it = b.lower_bound((n - sz[v]) / 2);
    if(it != b.end()) {
      int y = *it;
      ans = min(ans, calc(sz[v], y, n - sz[v] - y));
//      cerr << "b " << v << " " << sz[v] << " " << y << " " << ans << endl;
    }    
    if(it != b.begin()) {
      --it;
      int y = *it;
      ans = min(ans, calc(sz[v], y, n - sz[v] - y));
//      cerr << "b " << v << " " << sz[v] << " " << y << " " << ans << endl;
    }
    dfs(v, u);
    
    a.erase(a.find(sz[u]));
  }
    b.insert(sz[u]);
}
void solve() {
  cin >> n;
  for(int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  ans = n + 1;
  pre_dfs(1, 0);
  dfs(1, 0);
  cout << ans;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  solve();
  return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 5156 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 5156 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5212 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4956 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 5156 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 2 ms 5212 KB Output is correct
8 Correct 2 ms 5212 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 123 ms 24204 KB Output is correct
12 Correct 128 ms 23944 KB Output is correct
13 Correct 90 ms 24480 KB Output is correct
14 Correct 101 ms 24320 KB Output is correct
15 Correct 132 ms 24148 KB Output is correct
16 Correct 91 ms 24100 KB Output is correct
17 Correct 101 ms 24224 KB Output is correct
18 Correct 121 ms 29268 KB Output is correct
19 Correct 95 ms 24152 KB Output is correct
20 Correct 125 ms 24144 KB Output is correct