Submission #1056871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056871		kachim2	The Xana coup (BOI21_xanadu)	C++17	5 / 100	1065 ms	5840 KiB

xanadu

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

    }
    for(long i = 1; i < 1<<(n); i++){
        auto flit = lit;
        long fi = i;
        long cnt = 0;
        long scntl= 0;
        while(fi!=0){
            if(fi&1){
                scntl++;
                for(auto j : tree[cnt]){
                    flit[j] = !flit[j];
                }
                flit[cnt] = ! flit[cnt];
            }
            fi>>=1;
            cnt++;
        }

        bool bad = 0;
        for(long i = 0; i < n; i++) if(flit[i]) bad=1;
        if(!bad){
            bst = min(bst, scntl);
        }
    }
    if(bst == LONG_MAX)
    cout << "impossible";
    else
    cout << bst;


}

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