Submission #1263419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263419		rtri	The Xana coup (BOI21_xanadu)	C++20	5 / 100	1095 ms	6216 KiB

xanadu

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

int n;
vector<vector<int>> adj;
vector<int> cameras;

int main() {
  cin >> n;

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

  cameras.resize(n);
  int def = 0;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    cameras[i] = a;
    if (a)
      def |= 1 << i;
  }

  int ans = 1e9;
  for (int mask = 0; mask < pow(2, n); mask++) {
    int curr = def;
    int count = 0;
    for (int i = 0; i < n; i++) {
      if (1 & (mask >> i)) {
        count++;
        curr ^= 1 << i;
        for (int u : adj[i])
          curr ^= 1 << u;
      }
    }
    if (curr == 0) {
      ans = min(ans, count);
    }
  }

  if (ans == 1e9)
    cout << "impossible" << endl;
  else
    cout << ans << endl;

  return 0;
}

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