Submission #1184111

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184111		reginox	The Xana coup (BOI21_xanadu)	C++20	100 / 100	36 ms	21632 KiB

xanadu

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e5+3;
int n;
vector<int> g[N];
bool st[N];

ll dp[N][2][2]; //(current bulb #, bulb off/on, switch off/on)
ll tp[2][2]; //temp dp

ll INF = 1e9+7;

void dfs(int u, int p){
  for(auto v:g[u]){
    if(v!=p) dfs(v, u);
  }

  if(st[u] == 0){
    dp[u][1][1] = 1;
    dp[u][1][0] = INF;
    dp[u][0][1] = INF;
  }
  else{
    dp[u][0][1] = 1;
    dp[u][0][0] = INF;
    dp[u][1][1] = INF;
  }

  for(auto v:g[u]){
    if(v==p)continue;
    for(int i = 0; i < 2; i++)
      for(int j = 0; j < 2; j++) tp[i][j] = INF;
    for(int s1 = 0; s1 < 2; s1++){
      for(int t1 = 0; t1 < 2; t1++){
        for(int s2 = 0; s2 < 2; s2++){
          for(int t2 = 0; t2 < 2; t2++){
            if((s2 ^ t1) != 0) continue;
            tp[s1^t2][t1] = min(tp[s1^t2][t1], dp[u][s1][t1] + dp[v][s2][t2]);
          }
        }
      }
    }
    swap(dp[u], tp);
  }
}
int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n;
  for(int i = 1; i < n; i++){
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for(int i = 1; i <= n; i++) cin >> st[i];
  dfs(1, 0);
  // for(int i = 1; i <= n; i++){
  //   cout << i << "\n";
  //   for(int s = 0; s < 2; s++){
  //     for(int t = 0; t < 2; t++){
  //       cout << (dp[i][s][t] >= 1e9? -1:dp[i][s][t]) << " ";
  //     }
  //     cout << "\n";
  //   }
  //   cout << "\n";
  // }
  cout << (min(dp[1][0][0], dp[1][0][1])>=INF?"impossible":to_string(min(dp[1][0][0], dp[1][0][1])));
  return 0;
}

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