Submission #1070492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070492		duckindog	The Xana coup (BOI21_xanadu)	C++17	0 / 100	40 ms	20052 KiB

xanadu

#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
int n;
vector<int> ad[N];
int a[N];

long long f[N][2][2], dp[2][2];
void dfs(int u, int p = -1) { 
  f[u][0][0] = f[u][0][1] = f[u][1][0] = f[u][1][1] = N;
  f[u][a[u]][0] = 0;
  f[u][a[u] ^ 1][1] = 1;

  for (const auto& v : ad[u]) { 
    if (v == p) continue;
    dfs(v, u);
    for (int i = 0; i < 2; ++i) { 
      for (int j = 0; j < 2; ++j) dp[i][j] = f[u][i][j];
    }

    for (int a = 0; a < 2; ++a) { 
      for (int b = 0; b < 2; ++b) { 
        auto& ret = f[u][a][b]; ret = N;
        for (int c = 0; c < 2; ++c) { 
          for (int d = 0; d < 2; ++d)
            if (b ^ c ^ 1) ret = min(ret, dp[a ^ d][b] + f[v][c][d]);
        }
      }
    }
  }
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;
  for (int i = 2; i <= n; ++i) { 
    int u, v; cin >> u >> v;
    ad[u].push_back(v);
    ad[v].push_back(u);
  }
  for (int i = 1; i <= n; ++i) cin >> a[i];

  dfs(1);
  
  int answer = min(f[1][0][0], f[1][0][1]);
  if (answer > n) cout << "imposible\n";
  else cout << answer << "\n";
}

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