Submission #1275227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275227		nanaseyuzuki	Power Plant (JOI20_power)	C++20	100 / 100	101 ms	24168 KiB

power

#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 2e5 + 5, bm = (1 << 11) + 1, mod = 1e9 + 7, offset = 5e4, B = 320 + 5;
const int inf = 1e9, base = 311;

vector <int> a[mn];
int n, dp[mn], on[mn], ans = 0;

void dfs(int u, int p){
    for(auto v : a[u]){
        if(v == p) continue;
        dfs(v, u);
    }
    int max_val = 0, sum = 0;
    for(auto v : a[u]){
        if(v == p) continue;
        sum += dp[v], max_val = max(max_val, dp[v]);
    }
    if(on[u]){
        ans = max(ans, max_val + 1);
        if(sum <= 1){
            dp[u] = 1;
            ans = max(ans, dp[u]);
        }
        else{
            dp[u] = sum - 1;
            ans = max(ans, dp[u]);
        }
    }
    else{
        dp[u] = sum;
        ans = max(ans, dp[u]);
    }
}

void solve(){
    cin >> n;
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    string s; cin >> s;
    s = "#" + s;
    for(int i = 1; i <= n; i++) on[i] = s[i] - '0';
    dfs(1, 0);
    cout << ans << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t --){
        solve();
    }
}

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