Submission #782714

#	Time	Username	Problem	Language	Result	Execution time	Memory
782714		kebine	The Xana coup (BOI21_xanadu)	C++17	100 / 100	49 ms	15560 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX = 1e5 + 5;

int N;
int c[MX];
vector<int> g[MX];
ll dp[MX][2][2];

void dfs(int v, int p) {
      if(g[v].size() == 1 && v != 1) {
            dp[v][c[v]][0] = 0;
            dp[v][c[v] ^ 1][1] = 1;

            return;     
      }

      for(auto u : g[v]) {
            if(u == p) continue;

            dfs(u, v);
      }


      ll sum = 0, cnt = 0, mn = 1e18;
      for(auto u : g[v]) {
            if(u == p) continue;

            if(dp[u][0][0] < dp[u][0][1]) {
                  sum += dp[u][0][0];
                  mn = min(mn, dp[u][0][1] - dp[u][0][0]);
            } else {
                  sum += dp[u][0][1];
                  mn = min(mn, dp[u][0][0] - dp[u][0][1]);
                  cnt++;
            }
      }

      cnt &= 1;
      dp[v][cnt ^ c[v]][0] = min(dp[v][cnt ^ c[v]][0], sum);
      cnt ^= 1;
      dp[v][cnt ^ c[v]][0] = min(dp[v][cnt ^ c[v]][0], sum + mn);

      sum = 0, cnt = 0, mn = 1e18;
      for(auto u : g[v]) {
            if(u == p) continue;

            if(dp[u][1][0] < dp[u][1][1]) {
                  sum += dp[u][1][0];
                  mn = min(mn, dp[u][1][1] - dp[u][1][0]);
            } else {
                  sum += dp[u][1][1];
                  mn = min(mn, dp[u][1][0] - dp[u][1][1]);
                  cnt++;
            }
      }

      cnt &= 1;
      cnt ^= 1;

      dp[v][cnt ^ c[v]][1] = min(dp[v][cnt ^ c[v]][1], sum + 1);
      cnt ^= 1;
      dp[v][cnt ^ c[v]][1] = min(dp[v][cnt ^ c[v]][1], sum + mn + 1);
}     

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

      for(int i = 0; i < MX; i++) 
            for(int j = 0; j < 2; j++)
                  for(int k = 0; k < 2; k++)
                        dp[i][j][k] = 1e18;

      cin >> N;
      for(int i = 0; i < N - 1; 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 >> c[i];

      dfs(1, 0);

      ll res = min(dp[1][0][0], dp[1][0][1]);

      if(res == 1e18) {
            cout << "impossible\n";
      } else {
            cout << res << '\n';
      }
}     

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