Submission #543342

#	Time	Username	Problem	Language	Result	Execution time	Memory
543342		RaresFelix	Power Plant (JOI20_power)	C++17	100 / 100	155 ms	30788 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;
	for(int i = 0; i < a.size(); ++i)
		On[i] = (a[i] == '1');
	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;
      |                      ^~
power.cpp: In function 'int main()':
power.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for(int i = 0; i < a.size(); ++i)
      |                 ~~^~~~~~~~~~

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