Submission #651699

#	Time	Username	Problem	Language	Result	Execution time	Memory
651699		tvladm2009	The Xana coup (BOI21_xanadu)	C++14	100 / 100	87 ms	20476 KiB

xanadu

#include <bits/stdc++.h>
///#pragma GCC target ("sse4.2")

///#pragma GCC optimize("O1")
///#pragma GCC optimize("O2")

///#pragma GCC optimize("O3")
///#pragma GCC optimize("Os")
///#pragma GCC optimize("Ofast")
///#pragma GCC target("avx,avx2,fma")
///#pragma GCC optimization ("unroll-loops")
///#pragma GCC target("avx2")

using namespace std;

typedef long long ll;
#define int ll

const int N = 1e5 + 7;
const int INF = 1e9;
int a[N], dp[N][2][2];
vector<int> g[N];

void dfs(int u, int p = -1) {
  int sum[2][2];
  sum[0][0] = sum[0][1] = 0;
  sum[1][0] = sum[1][1] = INF;
  for (auto &it : g[u]) {
    if (it != p) {
      dfs(it, u);
      int old[2][2];
      old[0][0] = sum[0][0];
      old[1][0] = sum[1][0];
      old[0][1] = sum[0][1];
      old[1][1] = sum[1][1];
      sum[0][0] = min({old[0][0] + dp[it][0][0], old[1][0] + dp[it][1][0], INF});
      sum[0][1] = min({old[0][1] + dp[it][0][1], old[1][1] + dp[it][1][1], INF});
      sum[1][0] = min({old[0][0] + dp[it][1][0], old[1][0] + dp[it][0][0], INF});
      sum[1][1] = min({old[0][1] + dp[it][1][1], old[1][1] + dp[it][0][1], INF});
    }
  }
  if (a[u] == 1) {
    dp[u][0][0] = sum[1][0];
    dp[u][0][1] = sum[0][0];
    dp[u][1][0] = sum[0][1] + 1;
    dp[u][1][1] = sum[1][1] + 1;
  } else {
    dp[u][0][0] = sum[0][0];
    dp[u][0][1] = sum[1][0];
    dp[u][1][0] = sum[1][1] + 1;
    dp[u][1][1] = sum[0][1] + 1;
  }
}

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

  int n;
  cin >> n;
  for (int i = 1; i <= n - 1; i++) {
    int x, y;
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  dfs(1);
  int ans = min(dp[1][0][0], dp[1][1][0]);
  if (ans == INF) {
    cout << "impossible";
    return 0;
  }
  cout << ans;
  return 0;
}

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