제출 #433297

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
433297		couplefire	The Xana coup (BOI21_xanadu)	C++17	100 / 100	112 ms	23116 KiB

xanadu

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

const int N = 100005;
const int INF = 0x3f3f3f3f;

int ckmin(int& x, int y){return x>y?x=y:x;}

int n;
vector<int> adj[N];
int arr[N];
int dp[N][2][2]; // vertex, value of the current node, whether this node is chosen

void dfs(int v, int p){
    int tmp[2][2][2];
    memset(tmp, INF, sizeof tmp);
    tmp[0][0][0] = tmp[0][1][0] = 0;
    for(auto u : adj[v]){
        if(u == p) continue;
        dfs(u, v);
        memset(tmp[1], INF, sizeof tmp[1]);
        for(int a = 0; a<2; a++) // dp & tmp
            for(int b = 0; b<2; b++) // dp
                for(int c = 0; c<2; c++) // tmp
                    ckmin(tmp[1][a][b^c], dp[u][a][b]+tmp[0][a][c]);
        swap(tmp[0], tmp[1]);
    }
    dp[v][0][0] = tmp[0][0][arr[v]];
    dp[v][0][1] = tmp[0][1][1^arr[v]]+1;
    dp[v][1][0] = tmp[0][0][1^arr[v]];
    dp[v][1][1] = tmp[0][1][arr[v]]+1;
}

int main(){
    // freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i<n-1; i++){
        int a, b; cin >> a >> b; --a; --b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i = 0; i<n; i++)
        cin >> arr[i];
    memset(dp, INF, sizeof dp);
    dfs(0, -1);
    int ans = min(dp[0][0][0], dp[0][0][1]);
    if(ans == INF) cout << "impossible" << '\n';
    else cout << ans << '\n';
}

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