Submission #525223

#	Time	Username	Problem	Language	Result	Execution time	Memory
525223		pokmui9909	The Xana coup (BOI21_xanadu)	C++17	100 / 100	56 ms	25168 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const ll INF = 1e9 + 7;
ll N;
vector<ll> G[100005];
ll C[100005];
ll D[100005][2][2];
void dfs(ll u, ll p){
    D[u][0][C[u]] = 0, D[u][1][C[u] ^ 1] = 1;
    D[u][0][C[u] ^ 1] = D[u][1][C[u]] = INF;
    for(auto v : G[u]){ 
        if(v == p) continue;
        dfs(v, u);
        ll T[2][2];
        for(int i = 0; i < 2; i++){
            for(int j = 0; j < 2; j++){
                T[i][j] = INF;
                for(int k = 0; k < 2; k++){
                    T[i][j] = min(T[i][j], D[u][i][j ^ k] + D[v][k][i]);
                }
            }
        }
        for(int i = 0; i < 2; i++){
            for(int j = 0; j < 2; j++){
                D[u][i][j] = T[i][j];
            }
        }
    }
}
 
int main(){
    cin.tie(0) -> sync_with_stdio(false);
 
    cin >> N;
    for(int i = 1; i < N; i++){
        ll 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, -1);
    ll r = min(D[1][0][0], D[1][1][0]);
    if(r <= N){
        cout << r << '\n';
    } else {
        cout << "impossible\n";
    }
}

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