Submission #1098214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098214		HasanV11010238	Power Plant (JOI20_power)	C++17	100 / 100	174 ms	29580 KiB

power

#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<vector<int>> v;
vector<ll> dp;
string s;
ll ans = 0;
void dfs(int x, int p){
    ll su = 0, mx = 0;
    for (auto el : v[x]){
        if (el != p){
            dfs(el, x);
            su += dp[el];
            mx = max(dp[el], mx);
        }
    }
    if (s[x] == '0'){
        dp[x] = su;
        ans = max(su, ans);
    }
    else{
        dp[x] = max(1LL, su - 1);
        ans = max(ans, max(mx + 1, su - 1));
    }
}
int main(){
    int n, a, b;
    cin>>n;
    v.resize(n + 1);
    dp.assign(n + 1, 0);
    for (int i = 0; i < n - 1; i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    cin>>s;
    s = " " + s;
    dfs(1, 0);
    cout<<ans;
}

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