oj.uz

Submission #1038454

# Submission time Handle Problem Language Result Execution time Memory
1038454 2024-07-29T19:57:11 Z vjudge1 Power Plant (JOI20_power) C++17
0 / 100
 2 ms 5168 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Incorrect 2 ms 5168 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Incorrect 2 ms 5168 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Incorrect 2 ms 5168 KB Output isn't correct
6 Halted 0 ms 0 KB -