Submission #543335

#	Time	Username	Problem	Language	Result	Execution time	Memory
543335		RaresFelix	Power Plant (JOI20_power)	C++17	0 / 100	4 ms	5048 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
	if(On[u - 1]) {
		r1 = -1; // il sparg
		for(auto [a, b] : F) r1 += a;
		r1 = max(r1, 1);
	} else
		for(auto [a, b] : F) r1 += a;
	//nimic de sus
	if(On[u - 1]) {
		int sa = 0, bb = 0, ba = 0;
		for(auto [a, b] : F) {
			bb = max(bb, b);
			ba = max(ba, a);
			sa += a;
		}
		r2 = max(bb, max(sa - 1, ba + 1));
		r2 = max(r2, 1);
	} else {
		int sa = 0, bb = 0;
		for(auto [a, b] : F) {
			bb = max(bb, b);
			sa += a;
		}
		r2 = max(bb, sa);
	}

	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;
}

Compilation message (stderr)

power.cpp: In function 'ii dp(int, int)':
power.cpp:10:22: warning: unused variable 'r3' [-Wunused-variable]
   10 |  int r1 = 0, r2 = 0, r3;
      |                      ^~

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