Submission #543329

#	Time	Username	Problem	Language	Result	Execution time	Memory
543329		RaresFelix	Power Plant (JOI20_power)	C++17	0 / 100	3 ms	5052 KiB

power

#include <bits/stdc++.h>
#define MN 200071

using namespace std;
int n;
vector<int> L[MN];
bitset<MN> On;
using ii = pair<int, int>;
ii dp(int u, int p) {
	int r1 = 0, r2 = 0, r3;
	vector<ii> F;
	for(auto it : L[u])
		if(it != p) F.push_back(dp(it, u));
	//ceva de sus
	for(auto [a, b] : F)
		r1 += a;
	r1 = max(r1, (int)On[u]);
	//nimic de sus
	for(auto [a, b] : F)
		r2 += b;
	r3 = On[u - 1];
	for(auto [a, b] : F)
		r3 += a;
	r2 = max(r2, r3);
	return {r1, r2};
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i = 1, u, v; i < n; ++i) {
		cin >> u >> v;
		L[u].push_back(v);
		L[v].push_back(u);
	}
	string a;
	cin >> a;
	On = bitset<MN>(a);
	auto [b, c] = dp(1, 0);
	cout << max(b, c) << "\n";
    return 0;
}

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