Submission #1129238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129238		vladilius	The Xana coup (BOI21_xanadu)	C++20	100 / 100	86 ms	27976 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int inf = 1e9;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n; cin>>n;
    vector<int> g[n + 1];
    for (int i = 1; i < n; i++){
        int x, y; cin>>x>>y;
        g[x].pb(y);
        g[y].pb(x);
    }
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>a[i];
    }
    
    int dp[n + 1][2][2];
    function<void(int, int)> dfs = [&](int v, int pr){
        for (int i: g[v]){
            if (i == pr) continue;
            dfs(i, v);
        }
        
        vector<int> all;
        ll tot = 0;
        for (int i: g[v]){
            if (i == pr) continue;
            tot += dp[i][a[i]][0];
            all.pb(dp[i][a[i]][1] - dp[i][a[i]][0]);
        }
        sort(all.begin(), all.end());
        vector<ll> p(all.size() + 1);
        for (int i = 1; i <= all.size(); i++){
            p[i] = p[i - 1] + all[i - 1];
        }
        
        vector<int> mn(2, inf);
        for (int i = 0; i <= all.size(); i++){
            mn[i % 2] = (int) min((ll) mn[i % 2], tot + p[i]);
        }
        
        dp[v][0][0] = mn[0];
        dp[v][1][0] = mn[1];
        
        all.clear();
        tot = 0;
        for (int i: g[v]){
            if (i == pr) continue;
            tot += dp[i][!a[i]][0];
            all.pb(dp[i][!a[i]][1] - dp[i][!a[i]][0]);
        }
        sort(all.begin(), all.end());
        for (int i = 1; i <= all.size(); i++){
            p[i] = p[i - 1] + all[i - 1];
        }
        
        mn[0] = mn[1] = inf;
        for (int i = 0; i <= all.size(); i++){
            mn[i % 2] = (int) min((ll) mn[i % 2], tot + p[i] + 1);
        }
        
        dp[v][0][1] = mn[1];
        dp[v][1][1] = mn[0];
    };
    dfs(1, 0);
    
    int out = min(dp[1][a[1]][0], dp[1][a[1]][1]);
    if (out == inf){
        cout<<"impossible"<<"\n";
    }
    else {
        cout<<out<<"\n";
    }
}

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