Submission #969343

#	Time	Username	Problem	Language	Result	Execution time	Memory
969343		_callmelucian	Power Plant (JOI20_power)	C++14	100 / 100	110 ms	30032 KiB

power

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 2e5 + 5;
int dp[2][mn], power[mn];
vector<int> adj[mn];

void dfs (int u, int p) {
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        dp[0][u] += max(0, dp[0][v]);
        dp[1][u] = max(dp[1][u], dp[0][v]);
    }
    dp[1][u] += power[u];
    dp[0][u] -= power[u];

    if (power[u])
        dp[0][u] = max(dp[0][u], 1);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
        char c; cin >> c;
        power[i] = c - '0';
    }
    dfs(1, 1);

    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 2; j++)
            ans = max(ans, dp[j][i]);
    cout << ans;

    return 0;
}

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