oj.uz

Submission #543335

# Submission time Handle Problem Language Result Execution time Memory
543335 2022-03-30T10:06:35 Z RaresFelix Power Plant (JOI20_power) C++17
0 / 100
 4 ms 5048 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 4 ms 5048 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 4 ms 5048 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Incorrect 4 ms 5048 KB Output isn't correct
4 Halted 0 ms 0 KB -