Submission #1029361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029361		MDario	The Xana coup (BOI21_xanadu)	C++17	100 / 100	41 ms	23128 KiB

xanadu

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

#define F first
#define S second
typedef long long ll;
typedef pair<pair<ll, ll>, pair<ll, ll>> Ans;

const string noyes[2] = {"NO", "YES"};
const ll INFLL = (1ll << 62);
const int INF = (1 << 30);
const int MAXN = 300'000;
const ll MOD = 1'000'000'007;

vector<int> g[MAXN];
int a[MAXN];

Ans f(int x, int ax) {
  Ans y = {{INF, 1}, {0, INF}};
  if (a[x])
    y = {{0, INF}, {INF, 1}};
  for (int i : g[x]) {
    if (i != ax) {
      // temporal y
      Ans ty = f(i, x);
      y = {{min(y.F.F + ty.S.F, y.S.F + ty.S.S),
            min(y.F.S + ty.F.F, y.S.S + ty.F.S)},
           {min(y.S.F + ty.S.F, y.F.F + ty.S.S),
            min(y.S.S + ty.F.F, y.F.S + ty.F.S)}};
    }
  }
  return y;
}

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

  int n;
  cin >> n;

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

  Ans ans = f(1, 0);
  ll final_ans = min(ans.S.F, ans.S.S);
  if (final_ans > n)
    cout << "impossible\n";
  else
    cout << min(ans.S.F, ans.S.S) << "\n";

  return 0;
}

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