Submission #894608

#	Time	Username	Problem	Language	Result	Execution time	Memory
894608		esomer	The Xana coup (BOI21_xanadu)	C++17	100 / 100	73 ms	15820 KiB

xanadu

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

#define int long long

const int N = 100000;
const int INF = 1e11;

vector<int> adj[N];
int dp[4][N]; //0 - I don't toggle. 1 - I toggle. 2, 3 - same but the camera is not off.
int initial[N];

void get0(int x, int p){
    if(initial[x] == 0){
        int ans = 0;
        vector<int> change;
        for(int node : adj[x]){
            if(node != p){
                ans += dp[0][node];
                change.push_back(dp[1][node] - dp[0][node]);
            }
        }
        sort(change.begin(), change.end());
        int mn = 0;
        int curr = 0;
        for(int i = 0; i + 1 < (int)change.size(); i += 2){
            curr += change[i] + change[i+1];
            mn = min(mn, curr);
        }
        dp[0][x] = ans + mn;
    }else{
        dp[0][x] = INF;
        int ans = 0;
        vector<int> change;
        for(int node : adj[x]){
            if(node != p){
                ans += dp[0][node];
                change.push_back(dp[1][node] - dp[0][node]);
            }
        }
        if(change.empty()) return;
        sort(change.begin(), change.end());
        int mn = change[0];
        int curr = change[0];
        for(int i = 1; i + 1 < (int)change.size(); i += 2){
            curr += change[i] + change[i+1];
            mn = min(mn, curr);
        }
        dp[0][x] = ans + mn;
    }
}

void get1(int x, int p){
    if(initial[x] == 1){
        int ans = 1;
        vector<int> change;
        for(int node : adj[x]){
            if(node != p){
                ans += dp[2][node];
                change.push_back(dp[3][node] - dp[2][node]);
            }
        }
        sort(change.begin(), change.end());
        int mn = 0;
        int curr = 0;
        for(int i = 0; i + 1 < (int)change.size(); i += 2){
            curr += change[i] + change[i+1];
            mn = min(mn, curr);
        }
        dp[1][x] = ans + mn;
    }else{
        dp[1][x] = INF;
        int ans = 1;
        vector<int> change;
        for(int node : adj[x]){
            if(node != p){
                ans += dp[2][node];
                change.push_back(dp[3][node] - dp[2][node]);
            }
        }
        if(change.empty()) return;
        sort(change.begin(), change.end());
        int mn = change[0];
        int curr = change[0];
        for(int i = 1; i + 1 < (int)change.size(); i += 2){
            curr += change[i] + change[i+1];
            mn = min(mn, curr);
        }
        dp[1][x] = ans + mn;
    }
}

void get2(int x, int p){
    if(initial[x] == 1){
        int ans = 0;
        vector<int> change;
        for(int node : adj[x]){
            if(node != p){
                ans += dp[0][node];
                change.push_back(dp[1][node] - dp[0][node]);
            }
        }
        sort(change.begin(), change.end());
        int mn = 0;
        int curr = 0;
        for(int i = 0; i + 1 < (int)change.size(); i += 2){
            curr += change[i] + change[i+1];
            mn = min(mn, curr);
        }
        dp[2][x] = ans + mn;
    }else{
        dp[2][x] = INF;
        int ans = 0;
        vector<int> change;
        for(int node : adj[x]){
            if(node != p){
                ans += dp[0][node];
                change.push_back(dp[1][node] - dp[0][node]);
            }
        }
        if(change.empty()) return;
        sort(change.begin(), change.end());
        int mn = change[0];
        int curr = change[0];
        for(int i = 1; i + 1 < (int)change.size(); i += 2){
            curr += change[i] + change[i+1];
            mn = min(mn, curr);
        }
        dp[2][x] = ans + mn;
    }
}

void get3(int x, int p){
    if(initial[x] == 0){
        int ans = 1;
        vector<int> change;
        for(int node : adj[x]){
            if(node != p){
                ans += dp[2][node];
                change.push_back(dp[3][node] - dp[2][node]);
            }
        }
        sort(change.begin(), change.end());
        int mn = 0;
        int curr = 0;
        for(int i = 0; i + 1 < (int)change.size(); i += 2){
            curr += change[i] + change[i+1];
            mn = min(mn, curr);
        }
        dp[3][x] = ans + mn;
    }else{
        dp[3][x] = INF;
        int ans = 1;
        vector<int> change;
        for(int node : adj[x]){
            if(node != p){
                ans += dp[2][node];
                change.push_back(dp[3][node] - dp[2][node]);
            }
        }
        if(change.empty()) return;
        sort(change.begin(), change.end());
        int mn = change[0];
        int curr = change[0];
        for(int i = 1; i + 1 < (int)change.size(); i += 2){
            curr += change[i] + change[i+1];
            mn = min(mn, curr);
        }
        dp[3][x] = ans + mn;
    }
}

void DFS(int x, int p){
    for(int node : adj[x]){
        if(node != p) DFS(node, x);
    }
    get0(x, p);
    get1(x, p);
    get2(x, p);
    get3(x, p);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; 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 >> initial[i];
    DFS(0, -1);
    if(min(dp[0][0], dp[1][0]) >= 1e6) cout << "impossible\n";
    else cout << min(dp[0][0], dp[1][0]) << "\n";
}

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