Submission #769408

#	Time	Username	Problem	Language	Result	Execution time	Memory
769408		raysh07	The Xana coup (BOI21_xanadu)	C++17	100 / 100	50 ms	18840 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e5 + 69;
int dp[N][2][2], a[N], n, ndp[2][2];
vector <int> adj[N];

void dfs(int u, int par = -1){
    //second index --> is subtree head off 
    //third index --> did you use operation at subtree head 
    
    dp[u][a[u]][0] = 0;
    dp[u][a[u] ^ 1][1] = 1;
    
    for (int v : adj[u]){
        if (v != par){
            dfs(v, u);
            ndp[0][0] = ndp[0][1] = ndp[1][0] = ndp[1][1] = INF;
            for (int s = 0; s < 2; s++){
                //current state of head 
                for (int op = 0; op < 2; op++){
                    //used op at current head or not 
                    for (int op1 = 0; op1 < 2; op1++){
                        //used op at child or not 
                        int need = op;
                        
                        ndp[s ^ op1][op] = min(ndp[s ^ op1][op], dp[u][s][op] + dp[v][need][op1]);
                    }
                }
            }
            
            for (int i = 0; i < 2; i++){
                for (int j = 0; j < 2; j++){
                    dp[u][i][j] = ndp[i][j];
                }
            }
        }
    }
    
    // cout << u << "\n";
    // for (int i = 0; i < 2; i++){
    //     for (int j = 0; j < 2; j++){
    //         cout << dp[u][i][j] << " ";
    //     }
    // }
    // cout << "\n";
}

void Solve() 
{
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    for (int i = 0; i < N; i++){
        for (int j = 0; j < 2; j++){
            for (int k = 0; k < 2; k++){
                dp[i][j][k] = INF;
            }
        }
    }
    
    dfs(1);
    
    int ans = INF;
    for (int i = 0; i < 1; i++){
        for (int j = 0; j < 2; j++){
            ans = min(ans, dp[1][i][j]);
        }
    }
    
    if (ans == INF) cout << "impossible\n";
    else cout << ans << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
//    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

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