Submission #582050

#	Time	Username	Problem	Language	Result	Execution time	Memory
582050		Vanilla	Power Plant (JOI20_power)	C++17	100 / 100	258 ms	28056 KiB

power

#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 2e5 + 2;
int n;
int ans = 0;
vector <int> ad [maxn];
string type;

int dp (int u, int p) {
    int rs0 = 0, rs1 = 0;
    for (int v: ad[u]) {
        if (v == p) continue;
        int k = dp(v, u);
        rs0+=k;
        rs1=max(rs1, k);
    }
    if (type[u] == '1') {
        ans = max({ans, rs1 + 1, rs0 - 1, 1});
        return max(rs0 - 1, 1);
    }
    ans = max(ans, rs0);
    return rs0;
}

int main() {
    cin >> n;
    for (int i = 0; i < n - 1; i++){
        int x,y;
        cin >> x >> y;
        x--;
        y--;
        ad[x].push_back(y);
        ad[y].push_back(x);
    }
    cin >> type;
    dp(0, -1);
    cout << ans;
    return 0;
}

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