Submission #378403

#	Time	Username	Problem	Language	Result	Execution time	Memory
378403		qwerty234	Power Plant (JOI20_power)	C++14	100 / 100	353 ms	32876 KiB

power

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back

using namespace std;

const int MAXN = 2e5 + 10, inf = 2e9;

int n, m, d[MAXN], dp[MAXN], a[MAXN];
vector <int> g[MAXN];

void dfs(int u, int p) {
  int smd = 0, mxdp = 0, mxd = 0;
  for (int to : g[u]) {
    if (to == p)
      continue;
    dfs(to, u);
    smd += d[to];
    mxdp = max(mxdp, dp[to]);
    mxd = max(mxd, d[to]);
  }
  d[u] = dp[u] = 0;
  d[u] = max(d[u], max(0, smd - a[u]));
  dp[u] = max(dp[u], max(mxdp, smd - a[u]));
  if (a[u] == 1) {
    d[u] = max(d[u], 1);
    dp[u] = max(dp[u], 1 + mxd);
  }
}

main() {
//  freopen("input.txt", "r", stdin);
  cin >> n;
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    g[u].pb(v);
    g[v].pb(u);
  }
  for (int i = 1; i <= n; i++) {
    char ch;
    cin >> ch;
    a[i] = ch - '0';
  }
  dfs(1, -1);
  cout << dp[1];
}

Compilation message (stderr)

power.cpp:33:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main() {
      |      ^

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