Submission #876598

#	Time	Username	Problem	Language	Result	Execution time	Memory
876598		floralfield	The Xana coup (BOI21_xanadu)	C++17	100 / 100	82 ms	30748 KiB

xanadu

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define keish                       \
      ios_base::sync_with_stdio(0); \
      cin.tie(0); cout.tie(0)

using namespace std;

signed main(){
      keish;

      int n;
      cin >> n;

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

      vector<int> a(n);
      for(int i = 0; i < n; i++) cin >> a[i];

      vector<bool> vis(n);
      vector dp(n, vector(2, vector<int>(2, n + 5)));

      function<void(int)> dfs = [&](int u){
            vis[u] = 1;

            if(!a[u]){
                  dp[u][0][0] = 0;
                  dp[u][1][1] = 1;
            }else{
                  dp[u][0][1] = 0;
                  dp[u][1][0] = 1;
            }

            for(auto v : e[u]){
                  if(!vis[v]){
                        dfs(v);

                        int x = dp[u][0][0];
                        int y = dp[u][0][1];
                        dp[u][0][0] = min(dp[v][0][0] + x, dp[v][1][0] + y);
                        dp[u][0][1] = min(dp[v][0][0] + y, dp[v][1][0] + x);

                        x = dp[u][1][0];
                        y = dp[u][1][1];
                        dp[u][1][0] = min(dp[v][0][1] + x, dp[v][1][1] + y);
                        dp[u][1][1] = min(dp[v][0][1] + y, dp[v][1][1] + x);
                  }
            }
      };

      dfs(0);

      if(min(dp[0][0][0], dp[0][1][0]) > n){
            cout << "impossible\n";
      }else{
            cout << min(dp[0][0][0], dp[0][1][0]) << '\n';
      }
}

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