Submission #1273529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273529		KindaGoodGames	The Xana coup (BOI21_xanadu)	C++20	5 / 100	1097 ms	5764 KiB

xanadu

#include<bits/stdc++.h>

using namespace std;

#define int long long

int32_t main(){
    int n;
    cin >> n;
    vector<vector<int>> adj(n);
    for(int i = 0; i < n-1LL; i++){
        int a,b;
        cin >> a >> b;
        a--;b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<bool> ostate(n);
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        ostate[i] = a;
    }

    int p2 = 1LL << n;
    int b = 1e9;

    for(int m = 0; m < p2; m++){
        vector<bool> state = ostate;
        for(int i = 0;i < n; i++){
            if(m & (1 << i)){
                state[i] = !state[i];
                for(auto u : adj[i]){
                    state[u] = !state[u];
                }
            }
        }
        bool valid = true;
        for(int i = 0; i < n; i++){
            if(state[i]){
                valid = false;
                break;
            }
        }
        if(valid){
            b = min(b, (long long)__builtin_popcount(m));
        }
    }
    if(b == 1e9){
        cout << "impossible\n";
    }else{
        cout << b << "\n";
    }
}

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