Submission #1056755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056755		kachim2	The Xana coup (BOI21_xanadu)	C++17	0 / 100	1097 ms	208724 KiB

xanadu

#include<bits/stdc++.h>
using namespace std;
vector<vector<long>> tree;
long N; long bst = LONG_MAX;
void x(vector<bool> lit, long n, long cnt){
    bool gud = 0;
    for(long i = 1; i <= N; i++) 
        if(lit[i]) gud = 1;
    if(!gud){
        bst = min(bst, cnt);
    }
    if(n==N+1) return;
    x(lit, n+1, cnt);
    lit[n] = !lit[n] ;
    for(auto i : tree[n]) lit[i] = !lit[i];
    x(lit, n+1, cnt+1);
}
int main(){
    long n;
    cin >> n;
    N=n;
    tree.resize(n+1);
    vector<bool> lit(n+1);
    for(long i = 0; i < n-1; i++){
        long a, b;
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    for(long i = 1; i <= n; i++){
        long x;cin >> x; lit[i] = x;

    }
    x(lit, 1, 0);
    if(bst == LONG_MAX)
    cout << "imposible";
    else
    cout << bst;


}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 40
• Subtask 5: 0 / 30