Submission #441198

#	Time	Username	Problem	Language	Result	Execution time	Memory
441198		peijar	Power Plant (JOI20_power)	C++17	100 / 100	176 ms	23860 KiB

power

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

const int MAXN = 2e5;

vector<int> adj[MAXN];
bitset<MAXN> hasPower;
int dp[MAXN][2]; // DP[curNode][onBefore]

int nbSommets;

void dfs(int u, int p) {
  for (int v : adj[u])
    if (v != p)
      dfs(v, u);

  // Put power :
  if (hasPower[u]) {
    dp[u][0] = 1;
    for (int v : adj[u])
      if (v != p)
        dp[u][0] = max(dp[u][0], 1 + dp[v][1]);
    dp[u][1] = 1;
  }
  // Don't put power :
  // Put power in only one place :
  for (int v : adj[u])
    if (v != p) {
      for (int b = 0; b < 2; ++b)
        dp[u][b] = max(dp[u][b], dp[v][b] - (b and hasPower[u]));
    }
  // Or put power in multiple places :
  int tot = 0;
  for (int v : adj[u])
    if (v != p)
      tot += dp[v][1];
  dp[u][0] = max(dp[u][0], tot - hasPower[u]);
  dp[u][1] = max(dp[u][1], tot - hasPower[u]);
}

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cin >> nbSommets;
  for (int i = 1; i < nbSommets; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  for (int i = 0; i < nbSommets; ++i) {
    char c;
    cin >> c;
    hasPower[i] = c == '1';
  }

  dfs(0, 0);
  cout << dp[0][0] << endl;
}

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