Submission #533676

#	Time	Username	Problem	Language	Result	Execution time	Memory
533676		kevinyang	The Xana coup (BOI21_xanadu)	C++17	100 / 100	75 ms	28248 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
const int mxn = 100005;
vector<int> adj[mxn];
int a[mxn];
int dp[2][2][mxn];//dp[used or not][node i is lit up or not][node i] = min cost to reach said state
void dfs(int u, int p){
    int c = 0;
    for(int nxt: adj[u]){
        if(nxt==p)continue;
        dfs(nxt,u);
        c++;
    }
    if(c==0){  
        if(a[u]==0){
            dp[0][0][u] = 0;
            dp[1][1][u] = 1;
            dp[0][1][u] = dp[1][0][u] = (int)1e9;
        }
        else{
            dp[0][0][u] = dp[1][1][u] = (int)1e9;
            dp[0][1][u] = 0;
            dp[1][0][u] = 1;
        }
    }
    else{
        vector<int>nodes;
        for(int nxt: adj[u]){
            if(nxt==p)continue;
            nodes.push_back(nxt);
        }
        dp[0][0][u] = dp[0][1][u] = dp[1][0][u] = dp[1][1][u] = (int)1e9;
        if(true){
            int sum = 0;
            vector<int>arr;
            for(int i = 0; i<c; i++){
                int x = dp[0][0][nodes[i]];
                int y = dp[1][0][nodes[i]];
                arr.push_back(y-x);
                sum+=x;
            }
            int cur = a[u]^1;
            sort(arr.begin(),arr.end());
            dp[1][cur][u] = min(dp[1][cur][u],sum+1);
            for(int i = 0; i<c; i++){
                cur^=1;
                sum+=arr[i];
                dp[1][cur][u] = min(dp[1][cur][u],sum+1);
            }
        }
        if(true){
            int sum = 0;
            vector<int>arr;
            for(int i = 0; i<c; i++){
                int x = dp[0][1][nodes[i]];
                int y = dp[1][1][nodes[i]];
                arr.push_back(y-x);
                sum+=x;
            }
            int cur = a[u];
            sort(arr.begin(),arr.end());
            dp[0][cur][u] = min(dp[0][cur][u],sum);
            for(int i = 0; i<c; i++){
                cur^=1;
                sum+=arr[i];
                dp[0][cur][u] = min(dp[0][cur][u],sum);
            }
        }
        /*
        for(int i = 0; i<(1LL<<c); i++){
            for(int j = 0; j<(1LL<<c); j++){
                int used = a[u];
                for(int a = 0; a<c; a++){
                    if(i&(1LL<<a)){
                        used^=1;
                    }
                }
                int sum = 0;
                int tot = 0;
                for(int a = 0; a<c; a++){
                    int x = (i&(1LL<<a));
                    int y = (j&(1LL<<a));
                    if(x>0)x = 1;
                    if(y>0)y = 1;
                    tot+=dp[x][y][nodes[a]];
                }
                for(int a = 0; a<c; a++){
                    if(j&(1LL<<a)){
                        sum++;
                    }
                }
                if(sum!=0&&sum!=c)continue;
                if(sum==0){
                    dp[1][used^1][u] = min(dp[1][used^1][u],tot+1);
                }
                else{
                    dp[0][used][u] = min(dp[0][used][u],tot);
                }
            }
        }
        */
    }
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i<n; i++){
        int x,y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for(int i = 1; i<=n; i++){
        cin >> a[i];
        a[i]^=1;
    }
    dfs(1,0);
    /*
    for(int i = 1; i<=n; i++){
        for(int a = 0; a<2; a++){
            for(int b = 0; b<2; b++){
                cout << dp[a][b][i] << " ";
            }
        }
        cout << "\n";
    }
    */
    int v = min(dp[0][1][1],dp[1][1][1]);
    if(v>(int)1e6)cout << "impossible\n";
    else cout << v << "\n";
    return 0;
}

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