Submission #1191959

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

power

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

using vll = vector<ll>;
using pll = pair<ll,ll>;

#define pb push_back
#define MP make_pair
#define f first
#define s second
#define mid ((l+r)>>1)
#define SZ(x) (int)(x.size())
#define MP make_pair
#define all(x) x.begin(), x.end()

const ll MAXN = 2e5 + 5;
const ll MOD = 998244353;
const ll INF = 1e16;

ll N, ans;
string S;
vll g[MAXN];
ll dp[MAXN], dp2[MAXN];

void solve(ll nodo, ll p) {
    ll aux;
    if (S[nodo - 1] == '1') { dp[nodo] = 1; aux = -1; }
    else { dp[nodo] = 0; aux = 0; }

    for (auto &it : g[nodo]) {
        if (it == p) continue;
        solve(it, nodo);

        dp[nodo] = max(dp[it] - ((S[nodo - 1] == '1' ? 1 : 0)), dp[nodo]);

        aux += dp[it];
    }
    dp[nodo] = max(dp[nodo], aux);

    dp2[nodo] = dp[nodo];
    for (auto &it : g[nodo]) {
        if (it == p) continue;
        dp2[nodo] = max(dp2[nodo], dp2[it]);
    }
}

void dfs(ll nodo, ll p) {
    if (nodo == p) solve(nodo, p);
    else {
        // recalcula del padre

        ll aux = -1;
        dp[p] = 1;
        for (auto &it : g[p]) {
            if (it == nodo) continue;

            dp[p] = max(dp[it], dp[p]);

            aux += dp[it];
        }
        dp[p] = max(dp[p], aux);

        // recalcula del nodo

        aux = -1;
        dp[nodo] = 1;
        for (auto &it : g[nodo]) {
            dp[nodo] = max(dp[it], dp[nodo]);

            aux += dp[it];
        }
        dp[nodo] = max(dp[nodo], aux);
    }

    ans = max(ans, dp[nodo]);

    for (auto &it : g[nodo]) {
        if (it == p) continue;
        dfs(it, nodo);
    }
}


void tc() {
    cin >> N;
    for (int i = 0; i < N - 1; i++) {
        ll a, b; cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }
    cin >> S;

    //dfs(1, 1);
    for (int i = 1; i <= N; i++) {
        solve(i, i);
        ans = max(ans, dp[i]);
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1; //cin >> t;
    while (t--) tc();
    return 0;
}

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