Submission #292623

#	Time	Username	Problem	Language	Result	Execution time	Memory
292623		kdh9949	Power Plant (JOI20_power)	C++17	100 / 100	262 ms	33464 KiB

power

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;

using vint = vector<int>;
using vll = vector<ll>;
using vld = vector<ld>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#define x first
#define y second
#define all(v) v.begin(),v.end()

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

  int n;
  cin >> n;

  vector<vint> e(n + 1);
  for(int i = 0; i < n - 1; i++) {
    int x, y;
    cin >> x >> y;
    e[x].push_back(y);
    e[y].push_back(x);
  }

  string s;
  cin >> s;
  vint a(n + 1);
  for(int i = 0; i < n; i++) a[i + 1] = (s[i] == '1');

  vint d(n + 1), tot(n + 1);
  function<int(int, int)> f = [&](int x, int y) {
    for(int i : e[x]) {
      if(i == y) continue;
      int t = f(i, x);
      tot[x] += t;
    }
    return d[x] = max(tot[x] - a[x], a[x]);
  };
  f(1, 0);

  int ans = min(2, int(count(all(a), 1)));
  function<void(int, int)> g = [&](int x, int y) {
    ans = max(ans, d[x]);
    for(int i : e[x]) {
      if(i == y) continue;
      int dx = d[x], di = d[i], tx = tot[x], ti = tot[i];
      tot[x] -= d[i];
      d[x] = max(tot[x] - a[x], a[x]);
      tot[i] += d[x];
      d[i] = max(tot[i] - a[i], a[i]);
      g(i, x);
      d[x] = dx; d[i] = di; tot[x] = tx; tot[i] = ti;
    }
  };
  g(1, 0);

  cout << ans << '\n';
  return 0;
}

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