Submission #1212850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212850		vyaduct	Power Plant (JOI20_power)	C++20	0 / 100	2 ms	4936 KiB

power

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

#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int mxN = 200'005;
vector<int> adj[mxN];
ll dp[mxN][2][2];
bool power[mxN];
// dp[n][on/off][there is/isn't a turned on child outside of his subtree]

void dfs(int s, int e) {
  ll mx1=0;
  ll mx2=0;
  ll sum=0;
  for (int u: adj[s]){
    if (u == e) continue;
    dfs(u, s);
    sum += max(dp[u][0][1], dp[u][1][1]);
    mx1 = max(dp[u][0][0], dp[u][1][0]);
    mx2 = max(dp[u][0][1], dp[u][1][1]);
  }
  dp[s][0][0] = max(sum-power[s], mx1);
  dp[s][0][1] = sum-power[s];
  dp[s][1][0] = mx2+power[s];
  dp[s][1][1] = power[s];
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n; cin >> n;
  for (int i = 0; i < n-1; i++) {
    int u, v; cin >> u >> v;
    adj[u].pb(v), adj[v].pb(u);
  }
  string s; cin>>s;
  for (int i=0;i<n;i++) power[i+1]=s[i]=='1';
  dfs(1, 0);
  cout << max(
    {dp[1][0][0], dp[1][0][1], dp[1][1][0], dp[1][1][1]}
    ) 
  << endl;
}

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