Submission #519872

#	Time	Username	Problem	Language	Result	Execution time	Memory
519872		erke	The Xana coup (BOI21_xanadu)	C++11	0 / 100	5 ms	4304 KiB

xanadu

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

typedef long long ll;

const int N = 100005;
const int oo = 1e9;

vector<int> adj[N];
int color[N], dp[N][2][2];

template<typename T>
void chmin(T &a, T b) {
  if (a > b) a = b;
}

void dfs(int i, int p) {
  if (color[i] == 0) {
    dp[i][0][0] = 0;
    dp[i][1][1] = 1;
  }
  else if (color[i] == 1) {
    dp[i][1][0] = 0;
    dp[i][0][1] = 1;
  }
  for (auto &j : adj[i]) {
    if (j == p) continue;
    dfs(j, i);
    array<array<int,2>,2> cur_dp;
    cur_dp[0][0] = min(dp[i][0][0] + dp[j][0][0], dp[i][1][0] + dp[j][0][1]);
    cur_dp[0][1] = min(dp[i][0][1] + dp[j][1][0], dp[i][1][1] + dp[j][1][1]);
    cur_dp[1][0] = min(dp[i][0][0] + dp[j][0][1], dp[i][1][0] + dp[j][0][0]);
    cur_dp[1][1] = min(dp[i][0][1] + dp[j][1][1], dp[i][1][1] + dp[j][1][0]);
    for (int k = 0; k <= 1; k++)
    for (int l = 0; l <= 1; l++) {
      if (cur_dp[k][l] >= oo) cur_dp[k][l] = oo;
      dp[i][k][l] = cur_dp[k][l];
    }
  }
  /*cerr << "i = " << i << '\n';
  for (int k = 0; k <= 1; k++)
  for (int l = 0; l <= 1; l++) {
    if (dp[i][k][l] >= oo) {
      cerr << "-" << " \n"[l == 1];
    }
    else cerr << dp[i][k][l] << " \n"[l == 1];
  }*/
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  freopen("xanadu.inp", "r", stdin);
  freopen("xanadu.out", "w", stdout);
  int n; cin >> n;
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) {
    cin >> color[i];
  }
  for (int i = 0; i < N; i++)
  for (int j = 0; j < 2; j++)
  for (int k = 0; k < 2; k++) {
    dp[i][j][k] = oo;
  }
  dfs(1, -1);
  int ans = min(dp[1][0][0], dp[1][0][1]);
  if (ans >= oo) cout << "impossible" << '\n';
  else cout << ans << '\n';
}

Compilation message (stderr)

xanadu.cpp: In function 'int main()':
xanadu.cpp:52:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   freopen("xanadu.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
xanadu.cpp:53:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |   freopen("xanadu.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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