Submission #292882

#	Time	Username	Problem	Language	Result	Execution time	Memory
292882		limabeans	Power Plant (JOI20_power)	C++17	6 / 100	1594 ms	23936 KiB

power

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;



int n;
vector<int> g[maxn];
string s;
set<int> broken;
int x,y;
bool dfs(int at, int p) {
    if (at==y) return true;
    for (int to: g[at]) {
	if (to==p) continue;
	if (dfs(to,at)) {
	    if (s[at]=='1' && at!=x) {
		broken.insert(at);
	    }
	    return true;
	}
    }
    return false;
}

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

    cin>>n;
    for (int i=0; i<n-1; i++) {
	int u,v; cin>>u>>v;
	--u; --v;
	g[u].push_back(v);
	g[v].push_back(u);
    }
    
    cin>>s;

    int best = 0;
    for (int mask=0; mask<1<<n; mask++) {
	vector<int> v;
	bool ok = true;
	for (int j=0; j<n && ok; j++) {
	    if (mask>>j&1) {
		if (s[j]=='0') ok=false;
		v.push_back(j);
	    }
	}
	if (!ok) continue;
	broken.clear();
	for (int i=0; i<int(v.size()); i++) {
	    for (int j=i+1; j<int(v.size()); j++) {
		x=v[i]; y=v[j];
		dfs(v[i],-1);
	    }
	}
	int res = 0;
	for (int x: v) {
	    if (!broken.count(x)) res++;
	}
	res -= int(broken.size());
	best = max(best, res);
    }

    cout<<best<<endl;    
    return 0;
}

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