Submission #296158

#	Time	Username	Problem	Language	Result	Execution time	Memory
296158		quocnguyen1012	Power Plant (JOI20_power)	C++14	100 / 100	189 ms	31608 KiB

power

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 2e5 + 5;

int N, f[maxn];
vector<int> adj[maxn];
bool mark[maxn];

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  cin >> N;
  for (int i = 1; i < N; ++i){
    int u, v; cin >> u >> v;
    adj[u].eb(v); adj[v].eb(u);
  }
  for (int i = 1; i <= N; ++i){
    char c; cin >> c;
    c -= '0'; mark[i] = c;
  }
  int res = 0;
  function<void(int, int)> dfs = [&](int u, int par)
  {
    int mx = 0;
    for (int v : adj[u]){
      if (v != par){
        dfs(v, u);
        f[u] += f[v];
        mx = max(mx, f[v] + 1);
      }
    }
    if(mark[u]){
      res = max(res, mx);
      f[u]--;
      f[u] = max(f[u], 1);
    }
    res = max(res, f[u]);
  };
  dfs(1, -1);
  cout << res;
}

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