Submission #1178196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178196		nguyenkhangninh99	Power Plant (JOI20_power)	C++17	100 / 100	82 ms	28104 KiB

power

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

#define int long long

const int maxn = 2e5 + 5;

vector<int> g[maxn];
int dp[maxn], ans;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
string s; 

void dfs(int u, int pre){
    int mx = 0;
    for(int v: g[u]){
        if(v == pre) continue;
        dfs(v, u);
        dp[u] += dp[v]; 
        mx = max(mx, dp[v]);
    }

    if(s[u - 1] == '1') dp[u] = max(dp[u] - 1, 1ll);
    ans = max({ans, dp[u], mx + (s[u - 1] == '1')});
}


void solve(){
    int n; cin >> n;

    for(int i = 1; i <= n - 1; i++){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    cin >> s;

    dfs(rng() % n + 1, 0);

    cout << ans;

}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    solve();
}

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