Submission #1148968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148968		cot7302	Power Plant (JOI20_power)	C++20	100 / 100	60 ms	19332 KiB

power

#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
using i64 = long long;
using namespace std;

template <class T>
using vec = vector<T>;

template <class T>
istream& operator>>(istream& is, vec<T>& X) {
  for (auto& x : X) {
    is >> x;
  }
  return is;
}

template <class T>
constexpr T infty = 0;

template <>
constexpr int infty<int> = 1'000'000'000;

template <>
constexpr i64 infty<i64> = 1'000'000'000'000'000'000;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N; cin >> N;
  vec<vec<int>> g(N);
  for (int i = 0; i < N - 1; i++) {
    int u, v; cin >> u >> v;
    u -= 1, v -= 1;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  string s; cin >> s;
  int ans{};
  auto dfs = [&](auto&& dfs, int x, int pre) -> int {
    int sum{}, mx{};
    for (auto to : g[x]) {
      if (to == pre) {
        continue;
      }
      int d = dfs(dfs, to, x);
      sum += d;
      mx = max(mx, d);
    }
    if (s[x] == '1') {
      ans = max(ans, mx + 1);
      ans = max(ans, sum - 1);
    }
    else {
      ans = max(ans, sum);
    }
    return max((int)(s[x] == '1'), max(mx, sum) - (s[x] == '1'));
  };
  dfs(dfs, 0, -1);
  cout << ans << '\n';
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 53 / 53