Submission #554479

#	Time	Username	Problem	Language	Result	Execution time	Memory
554479		Marceantasy	The Xana coup (BOI21_xanadu)	C++17	100 / 100	79 ms	21588 KiB

xanadu

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

#define ll long long
#define ar array

const int mxN = 1e5+1, M = 1e9+7;
int n, f[mxN]; 
vector<int> adj[mxN]; 

struct node{
    int a[2][2];
    node(){
        memset(a, 0x3f, sizeof(a));
    }
    node operator+(const node &x){
        node ret; 
        for(int i = 0; i<2; ++i){
            for(int j = 0; j<2; ++j){
                for(int k = 0; k<2; ++k){
                    ret.a[i][j^k] = min(ret.a[i][j^k], a[i][j] + x.a[i][k]);
                }
            }
        }
        return ret;
    }
}dp[mxN];

void dfs(int u, int p = -1){
    node cur;
    cur.a[0][0] = 0; 
    cur.a[1][1] = 1;
    for(int v : adj[u]){
        if(v == p) continue;
        dfs(v, u); 
        node flag;
        for(int i = 0; i<2; ++i){
            for(int j = 0; j<2; ++j){
                flag.a[f[v]^j][i] = dp[v].a[i][j];
            }
        }
        cur = cur+flag;
    }
    dp[u] = cur;
}

int main(){
#ifdef _DEBUG
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
    std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);

    cin >> n; 
    for(int i = 0; i<n-1; ++i){
        int u, v; 
        cin >> u >> v, --u, --v; 
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i = 0; i<n; ++i){
        cin >> f[i];
    }
    dfs(0);
    int ans = min(dp[0].a[0][f[0]], dp[0].a[1][f[0]]);
    if(ans >= (int)1e7){
        cout << "impossible\n";
    }else{
        cout << ans;
    }
}

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