Submission #783598

#	Time	Username	Problem	Language	Result	Execution time	Memory
783598		christinelynn	The Xana coup (BOI21_xanadu)	C++17	0 / 100	1081 ms	33164 KiB

xanadu

#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
int n;
vector<int> c;
vector<vector<int>> adj;
vector<vector<vector<int>>> dp;
int dfs(int u, int turn, int on, int p=-1) {
  if(dp[u][turn][on]<INF) return dp[u][turn][on];
  int &ret=dp[u][turn][on];
  if(adj[u].size()==1 && u) {
    if(turn && on!=c[u]) return ret=1;
    if(!turn && on==c[u]) return ret=0;
    return ret=INF;
  }
  int st=0, sum=0, mn=INF;
  for(int pp : adj[u]) {
    if(pp==p) continue;
    if(dp[pp][0][turn]<dp[pp][1][turn])
      sum+=dfs(pp, 0, turn, u),
      mn=min(mn, dfs(pp, 1, turn, u)-dfs(pp, 0, turn, u));
    else 
      sum+=dfs(pp, 1, turn, u), st^=1,
      mn=min(mn, dfs(pp, 0, turn, u)-dfs(pp, 1, turn, u));
  }
  if((c[u]^turn^st)==on) {
    if(sum>=INF) return ret=INF;
    return ret=turn+sum;
  } sum+=mn;
  if(sum>=INF) return ret=INF;
  return ret=turn+sum;
}
int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n; adj.resize(n); c.resize(n);
  dp.resize(n, vector<vector<int>>(2, vector<int>(2)));
  for(auto &p : dp) for(auto &pp : p) for(int &ppp : pp) ppp=INF;
  for(int i=1; i<n; i++) {
    int u, v; cin >> u >> v; --u; --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  } for(int &p : c) cin >> p;
  if(min(dfs(0, 0, 0), dfs(0, 1, 0))<INF) cout << min(dfs(0, 0, 0), dfs(0, 1, 0)) << '\n';
  else cout << "impossible\n";
    return 0;
}

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