Submission #997331

#	Time	Username	Problem	Language	Result	Execution time	Memory
997331		DanielPr8	Power Plant (JOI20_power)	C++14	100 / 100	80 ms	31384 KiB

power

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvl = vector<vll>;
using vb = vector<bool>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vvp = vector<vpl>;
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(),v.end()
vvl g;
vb gen;
vll dp0, dp1;
ll ans = 0;
void dfs(ll cur, ll par){
    if(!gen[cur]){
        for(ll i:g[cur]){
            if(i==par)continue;
            dfs(i, cur);
            dp0[cur]+=dp0[i];
            dp1[cur] = max(dp1[cur], dp1[i]);
        }
    }
    else{
        ll mx=0;
        for(ll i:g[cur]){
            if(i==par)continue;
            dfs(i, cur);
            dp0[cur]+=dp0[i];
            dp1[cur] = max(dp1[cur], dp1[i]);
            mx = max(mx, dp0[i]);
        }
        dp0[cur] = max(dp0[cur]-1, 1ll);
        dp1[cur] = max(dp1[cur]-1, mx+1);
    }
    ans = max(ans, max(dp0[cur], dp1[cur]));
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);
    ll n, a, b; cin >> n;
    g = vvl(n+1, vll());
    gen = vb(n+1);
    dp0=dp1=vll(n+1);
    for(ll i = 0; i < n-1; ++i){
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
    string s;
    cin >> s;
    for(ll i = 1; i <= n; ++i)if(s[i-1]=='1')gen[i]=1;
    dfs(1,0);
    cout << ans;
}

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