Submission #1124141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124141		Zero_OP	The Xana coup (BOI21_xanadu)	C++17	20 / 100	374 ms	60096 KiB

xanadu

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e5 + 5;

int N, c[MAX];
vector<int> adj[MAX];

namespace subtask1{
    bool check(){
        return N <= 20;
    }

    int msk[MAX];

    void solve(){
        int base = 0;
        for(int i = 0; i < N; ++i){
            base ^= c[i] * (1 << i);
        }

        for(int i = 0; i < N; ++i){
            msk[i] = (1 << i);
            for(auto j : adj[i]) msk[i] |= (1 << j);
        }

        int ans = N + 1;
        for(int mask = 0; mask < (1 << N); ++mask){
            int cur = base;
            for(int i = 0; i < N; ++i){
                if(mask >> i & 1) cur ^= msk[i];
            }

            if(cur == 0) {
                ans = min(ans, __builtin_popcount(mask));
            }
        }

        if(ans == N + 1) cout << "impossible\n";
        else cout << ans << '\n';
    }
}

namespace subtask2{
    bool check(){
        return N <= 40;
    }

    long long msk[MAX];

    vector<pair<long long, int>> compress(const vector<pair<long long, int>>& x){
        vector<pair<long long, int>> y;
        for(int i = 0; i < (int)x.size(); ++i){
            if(i == 0 || x[i - 1].first != x[i].first) y.push_back(x[i]);
        }
        return y;
    }

    void solve(){
        long long base = 0;
        for(int i = 0; i < N; ++i){
            if(c[i]) base ^= (1LL << i);
        }

        for(int i = 0; i < N; ++i){
            msk[i] = 1LL << i;
            for(int j : adj[i]) msk[i] ^= (1LL << j);
        }

        int sz_left = N / 2, sz_right = N - sz_left;
        vector<pair<long long, int>> l, r;
        for(int mask = 0; mask < (1 << sz_left); ++mask){
            long long cur = 0;
            for(int i = 0; i < sz_left; ++i){
                if(mask >> i & 1) cur ^= msk[i];
            }

            l.emplace_back(cur, __builtin_popcount(mask));
        }

        for(int mask = 0; mask < (1 << sz_right); ++mask){
            long long cur = 0;
            for(int i = 0; i < sz_right; ++i){
                if(mask >> i & 1) cur ^= msk[sz_left + i];
            }

            r.emplace_back(cur, __builtin_popcount(mask));
        }

        sort(l.begin(), l.end());
        sort(r.begin(), r.end());

        vector<pair<long long, int>> candidates = compress(l);

        int ans = N + 1;
        long long lst = -1;
        for(auto [mask, cost] : r){
            if(lst == mask) continue;
            lst = mask;

            mask ^= base;

            int l = 0, r = (int)candidates.size() - 1, pos = -1;
            while(l <= r){
                int mid = l + r >> 1;
                if(candidates[mid].first == mask){
                    pos = mid;
                    break;
                } else if(candidates[mid].first < mask) {
                    l = mid + 1;
                } else r = mid - 1;
            }

            if(pos != -1){
                ans = min(ans, cost + candidates[pos].second);
            }
        }

        if(ans == N + 1) cout << "impossible\n";
        else cout << ans << '\n';
    }
}

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

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    cin >> N;
    for(int i = 1; i < N; ++i){
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].emplace_back(v); adj[v].emplace_back(u);
    }

    for(int i = 0; i < N; ++i) cin >> c[i];

    if(subtask1::check()) return subtask1::solve(), 0;
    if(subtask2::check()) return subtask2::solve(), 0;
    return 0;
}

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