Submission #365155

#	Time	Username	Problem	Language	Result	Execution time	Memory
365155		ronnith	Power Plant (JOI20_power)	C++14	6 / 100	27 ms	492 KiB

power

#include <bits/stdc++.h>

using namespace std;

const int N = 16;
int n, mr[N], sz[N];
vector<int> adj[N];
string s;

void dfs1(int x, int pr) {
	sz[x] = (mr[x] == 1 && s[x] == '1'); 
	for(auto e : adj[x]) {
		if(e != pr) {
			dfs1(e, x);
			sz[x] += sz[e];
		}
	}
}

int res = 0;

void dfs2(int x, int pr) {
	int cnt = (sz[0] - sz[x] > 0);
	for(auto e : adj[x]) {
		if(e != pr) {
			cnt += (sz[e] > 0);
			dfs2(e, x);
		}
	}
	if(s[x] == '1' && mr[x] && !(cnt > 1)) res ++;
	if(s[x] == '1' && (cnt > 1)) res --;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;
	for(int i = 0;i < n - 1;i ++) {
		int x, y; 
		cin >> x >> y; 
		x --,y --;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	cin >> s;
	
	int ans = 0;
	int ans_mask = -1;

	for(int mask = 0;mask < (1<<n);mask ++) {
		for(int i = 0;i < n;i ++) {
			if(((1<<i)&mask) && s[i] == '1') {
				mr[i] = 1;
			} else {
				mr[i] = 0;
			}
		}
		res = 0;
		dfs1(0, -1);
		dfs2(0, -1);
		if(res > ans) {
			ans = res;
			ans_mask = mask;
		}
	}

	cout << ans << '\n';
}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:49:6: warning: variable 'ans_mask' set but not used [-Wunused-but-set-variable]
   49 |  int ans_mask = -1;
      |      ^~~~~~~~

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