oj.uz

Submission #543329

# Submission time Handle Problem Language Result Execution time Memory
543329 2022-03-30T09:50:12 Z RaresFelix Power Plant (JOI20_power) C++17
0 / 100
 3 ms 5052 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
	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.0 / 6.0

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

Subtask #2
0.0 / 41.0

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

Subtask #3
0.0 / 53.0

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