Submission #293711

#	Time	Username	Problem	Language	Result	Execution time	Memory
293711		arman_ferdous	Power Plant (JOI20_power)	C++17	100 / 100	243 ms	26872 KiB

power

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

#define fi first
#define se second
#define pb push_back
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define dbg(x) cerr << #x << " is " << x << "\n";

using ll = long long;
using ii = pair<ll,ll>;

const int N = 2e5+10;

int n;
vector<int> g[N];
char s[N];

int dp[2][N];

void solve(int u, int f) {
  int childcnt = 0;
  for(int v : g[u]) if(v != f) {
    childcnt++;
    solve(v, u);
  }
  if(childcnt == 0) {
    dp[0][u] = dp[1][u] = (s[u] == '1');
    return;
  }
  if(s[u] == '0') {
    dp[0][u] = 0;
    for(int v : g[u]) if(v != f)
      dp[0][u] = max(dp[0][u], dp[0][v]);
    dp[1][u] = 0;
    for(int v : g[u]) if(v != f)
      dp[1][u] += dp[1][v];
  }
  else {
    int on = 1, off = 0;

    off = 0;
    for(int v : g[u]) if(v != f)
      off = max(off, dp[0][v]);

    for(int v : g[u]) if(v != f)
      on = max(on, dp[1][v] + 1);
    dp[0][u] = max(on, off);

    dp[1][u] = -1;
    for(int v : g[u]) if(v != f)
      dp[1][u] += dp[1][v];
    dp[1][u] = max(1, dp[1][u]);
  }
}

int main() {
  scanf("%d", &n);
  for(int i = 1; i < n; i++) {
    int u, v; scanf("%d %d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  scanf(" %s", s + 1);
  solve(1, 0);
  printf("%d\n", max(dp[0][1], dp[1][1]));
  return 0;
}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
power.cpp:61:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |     int u, v; scanf("%d %d", &u, &v);
      |               ~~~~~^~~~~~~~~~~~~~~~~
power.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |   scanf(" %s", s + 1);
      |   ~~~~~^~~~~~~~~~~~~~

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