Submission #1038454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038454		vjudge1	Power Plant (JOI20_power)	C++17	0 / 100	2 ms	5168 KiB

power

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 2e5+7;
ll n, cost[mxn], dp[mxn][2][2];
// i / i's state / turned on any node in i's subtree
bool c[mxn];
vector<vector<ll>> g(mxn);
void dfs(ll u, ll v)
{
    ll cnt_d = 0;
    for (ll i : g[u]) if (i != v)
    {
        dfs(i,u);
        cnt_d += cost[i];
    }
    if (c[u]) cost[u] = max(1LL, cnt_d-1);
    else cost[u] = cnt_d;
    cerr << u << ' ' << cost[u] << '\n';
}
void dfs_dp(ll u, ll v)
{
    for (ll i : g[u]) if (i != v)
    {
        dfs_dp(i,u);
        dp[u][0][0] += dp[i][0][0];
        ll opt = max({dp[i][0][1], dp[i][1][1]});
        if (c[u]) opt = max(opt, dp[i][0][0]);
        dp[u][0][1] += opt;
        dp[u][1][1] += cost[i];
    }
    if (dp[u][0][1] >= 2 && c[u]) dp[u][0][1]--; 
    if (c[u]) dp[u][1][1]++;
    // cerr << u << ' ' << dp[u][0][0] << ' ' << dp[u][0][1] << ' ' << dp[u][1][1] << '\n';
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
    cin >> n;
    for (ll i = 1; i < n; i++)
    {
        ll a, b; cin >> a >> b;
        g[a].pb(b); g[b].pb(a);
    }
    string s; cin >> s;
    for (ll i = 1; i <= n; i++) c[i] = (s[i-1]-'0');
    dfs(1,1); dfs_dp(1,1); 
    cout << max({dp[1][0][0], dp[1][0][1], dp[1][1][1]});
}

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