Submission #1071841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071841		kilikuma	The Xana coup (BOI21_xanadu)	C++14	100 / 100	49 ms	18516 KiB

xanadu

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef DEBUG 
  #include "/home/ioi/contests/debug.h"
#else 
  #define debug(...) void(37)
#endif
 
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<vector<int>> g(N);
  for (int i = 0; i < N - 1; ++i) {
    int A, B;
    cin >> A >> B;
    --A, --B;
    g[A].push_back(B);
    g[B].push_back(A);
  }
  vector<int> S(N);
  for (int i = 0; i < N; ++i) {
    cin >> S[i];
  }
  using D = array<array<int, 2>, 2>;
  auto Dfs = [&](int v, auto&& Dfs) -> D {
    D cur{};
    for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) cur[i][j] = N + 1;  
    cur[S[v]][0] = 0;
    cur[S[v] ^ 1][1] = 1;
    bool leaf = true;
    for (auto u : g[v]) {
      g[u].erase(find(g[u].begin(), g[u].end(), v));
      auto c = Dfs(u, Dfs);
      D next{};
      for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) next[i][j] = N + 1;
      for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) for (int ii = 0; ii < 2; ++ii) {
        next[i ^ ii][j] = min(next[i ^ ii][j], cur[i][j] + c[j][ii]);
      }
      swap(next, cur);
      leaf = false;
    }
    return cur;
  };
  auto ans = Dfs(0, Dfs);
  int mn = min(ans[0][0], ans[0][1]);
  cout << (mn <= N ? to_string(mn) : "impossible") << '\n';
}
 

Compilation message (stderr)

xanadu.cpp: In instantiation of 'main()::<lambda(int, auto:1&&)> [with auto:1 = main()::<lambda(int, auto:1&&)>&; D = std::array<std::array<int, 2>, 2>]':
xanadu.cpp:48:24:   required from here
xanadu.cpp:34:10: warning: variable 'leaf' set but not used [-Wunused-but-set-variable]
   34 |     bool leaf = true;
      |          ^~~~

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