Submission #472112

#	Time	Username	Problem	Language	Result	Execution time	Memory
472112		PurpleCrayon	The Xana coup (BOI21_xanadu)	C++17	100 / 100	141 ms	34212 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int MAXN = 1e5+10, MOD = 1e9+7;
const int INF = 1e9+10;

int n, a[MAXN];
vector<int> adj[MAXN];

ar<ar<int, 2>, 2> dfs(int c, int p) { //par flipped[me flipped]
    vector<ar<ar<int, 2>, 2>> sub;
    for (auto nxt : adj[c]) if (nxt != p) sub.push_back(dfs(nxt, c));

    ar<ar<int, 2>, 2> ans;
    for (int rep : {0, 1}) {
        for (int me : {0, 1}) {
            ans[rep][me] = INF;

            ll base = 0;
            vector<ll> v;
            for (auto x : sub) {
                base += x[me][0];
                v.push_back(x[me][1]-x[me][0]);
            }
            sort(v.begin(), v.end());
            for (int i = 1; i < sz(v); i++) v[i] += v[i-1];
            for (int cnt = a[c]; cnt <= sz(v); cnt += 2) {
                ll cost = base + me;
                if (cnt) cost += v[cnt-1];

                ans[rep][me] = min<ll>(ans[rep][me], cost);
            }

            a[c] ^= 1;
        }
        a[c] ^= 1;
    }
    return ans;
}
void solve() {
    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 >> a[i];
    auto dp = dfs(0, -1);
    int ans = min(dp[0][0], dp[0][1]);
    if (ans >= INF) cout << "impossible\n";
    else cout << ans << '\n';
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int T=1;
    //cin >> T;
    while (T--) solve();
}

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