Submission #1287933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287933		behrad	The Xana coup (BOI21_xanadu)	C++17	100 / 100	91 ms	26624 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
// * No One Dies a Virgin, Life Fucks Us All
typedef long long ll;
#define nl '\n'
#define ff first
#define ss second
#define pb push_back
#define sik(x) {cout << x << nl; return;}
constexpr ll maxn = 1e5+10, mod = 1e9 + 7, inf = 1e17, SQ = 450, LG = 20;
typedef pair<int, int> pii;

int n, dp[maxn][2][2], a[maxn];
vector<int> g[maxn];

void dfs(int v, int p = 0) {
  vector<int> ch;
  for (int u : g[v]) {
    if (u != p) {
      dfs(u, v);
      ch.pb(u);
    }
  }

  if (ch.empty()) {
    dp[v][0][0] = 0;
    dp[v][1][1] = 1;
    return;
  }

  for (int val = 0; val < 2; ++val) {
    vector<int> pd(2, 2 * n);
    pd[val] = val;
    
    for (auto u : ch) {
      vector<int> cur(2, 2 * n);
      for (int i : {0, 1})
        for (int t : {0, 1})
          for (int s : {0, 1})
            if (s ^ val == a[u]) cur[i ^ t] = min(cur[i ^ t], pd[i] + dp[u][t][s]); 
          
      pd.swap(cur);
    }

    dp[v][val][0] = min(dp[v][val][0], pd[0]);
    dp[v][val][1] = min(dp[v][val][1], pd[1]);
  }
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0); 
  memset(dp, 31, sizeof dp);
  cin >> n;
  for (int i = 1 , u, v ; i < n ; i ++) {
    cin >> u >> v;
    g[u].pb(v);
    g[v].pb(u);
  }
  for (int i = 1 ; i <= n ; i ++) cin >> a[i];
  dfs(1);

  int res = min(dp[1][0][a[1]], dp[1][1][a[1]]);
  if (res > n) cout << "impossible\n";
  else cout << res << nl;
}

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