Submission #1189159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189159		lopkus	Papričice (COCI20_papricice)	C++20	50 / 110	1095 ms	15484 KiB

papricice

#include <bits/stdc++.h>

void solve() {
  int n;
  std::cin >> n;
  std::vector<std::vector<int>> adj(n + 1);
  std::vector<std::array<int, 2>> edg;
  for(int i = 1; i < n; i++) {
    int u, v;
    std::cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
    edg.push_back({u, v});
  }
  std::vector<int> sub_tree(n + 1, 1);
  std::vector<int> in(n + 1), out(n + 1);
  int t = 0;
  std::function<void(int, int)> dfs = [&] (int v, int p) {
    in[v] = t++;
    for(auto u : adj[v]) {
      if(u == p) {
        continue;
      }
      dfs(u, v);
      sub_tree[v] += sub_tree[u];
    }
  };
  dfs(1, 0);
  for(int i = 1; i <= n; i++) {
    out[i] = in[i] + sub_tree[i] - 1;
  }
  std::function<int(int, int)> in_subtree = [&] (int u, int v) {
    return in[u] <= in[v] && out[u] >= out[v];
  };
  int ans = n + 1;
  for(int u = 1; u <= n; u++) {
    for(int v = u + 1; v <= n; v++) {
      if(in_subtree(u, v)) {
        int A = sub_tree[u] - sub_tree[v];
        int B = sub_tree[v];
        int C = n - sub_tree[u];
        ans = std::min(ans, std::max({A, B, C}) - std::min({A, B, C}));
        continue;
      }
      if(in_subtree(v, u)) {
        int A = sub_tree[v] - sub_tree[u];
        int B = sub_tree[u];
        int C = n - sub_tree[v];
        ans = std::min(ans, std::max({A, B, C}) - std::min({A, B, C}));
        continue;
      }
      int A = sub_tree[u];
      int B = sub_tree[v];
      int C = n - (A + B);
      ans = std::min(ans, std::max({A, B, C}) - std::min({A, B, C}));
    }
  }
  std::cout << ans;
}


int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int t = 1;
  //std::cin >> t;
  while (t--) {
      solve();
  }

  return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 35 / 35
• Subtask 3: 0 / 60