Submission #1263541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263541		NikoBaotic	Power Plant (JOI20_power)	C++20	6 / 100	19 ms	328 KiB

power

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

#define all(x) x.begin(), x.end()
#define sz(x) ((int) ((x).size()))
#define pb push_back
#define F first
#define S second
#define FIO ios_base::sync_with_stdio(false); cin.tie(0)

const int N = 20;

int n;
vector<int> adj[N];
string s;
int par[N];
bool on[N];

int calc;
int cn[N];

int cnt(int node) {
	int sum = 0;

	if (on[node]) sum++;

	for (int x : adj[node]) {
		if (x == par[node]) continue;
		par[x] = node;

		sum += cnt(x);
	}

	cn[node] = sum;
	return sum;
}

int dfs(int node, bool o) {
	int has = 0;

	bool no = o;

	int t = 0;

	for (int x : adj[node]) {
		if (x == par[node]) continue;

		t += min(1, cn[x]);
	}

	if (t >= 2 or on[node]) no = 1;

	for (int x : adj[node]) {
		if (x == par[node]) continue;

		has += min(1, dfs(x, no));
	}

	if (o) has++;

	if (on[node] and has <= 1) {
		calc++;
	} else if (has >= 2 and s[node - 1] == '1') {
		calc--;
	}

	if (o) has--;

	return min(has + on[node], 1);
}

int main() {
	FIO;
	
	cin >> n;

	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;

		adj[a].pb(b);
		adj[b].pb(a);
	}

	cin >> s;

	int ans = 0;

	for (int i = 0; i < (1 << n); i++) {
		calc = 0;

		for (int j = 0; j < n; j++) {
			if (((1 << j) & i) and s[j] == '1') {
				on[j + 1] = 1;
			} else {
				on[j + 1] = 0;
			}
		}

		cnt(1);
		dfs(1, 0);

		ans = max(ans, calc);
	}

	cout << ans << endl;

	return 0;
}

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