Submission #1038458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038458		vjudge1	Power Plant (JOI20_power)	C++17	100 / 100	83 ms	27168 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, dp[mxn], ans = 0;
vector<vector<ll>> g(mxn);
bool c[mxn];
void dfs(ll u, ll v)
{
    for (ll i : g[u]) if (i != v)
    {
        dfs(i,u);
        dp[u] += dp[i];
        ans = max(ans, dp[i]+c[u]);
    }
    dp[u] = max(dp[u]-c[u], (ll)c[u]);
    ans = max(ans, dp[u]);
}
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); cout << ans;
}

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