Submission #860830

#	Time	Username	Problem	Language	Result	Execution time	Memory
860830		Cookie	The Xana coup (BOI21_xanadu)	C++14	100 / 100	81 ms	27984 KiB

xanadu

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define vt vector
#define pb push_back
#define pii pair<int, int>
#define sz(dq) (int)dq.size()
#define forr(i, a, b) for(int i = a; i < b; i++)
#define fi first
#define se second
#define pll pair<ll, ll>
ifstream fin("invtree.inp");
ofstream fout("invtree.out");
const ll mxn = 1e5 + 5, inf = 1e9, mod = 1e9 + 7, sq = 800, mxv = 1e6 + 5, pr = 37, mod2 = 1e9 + 9, mod3 = 998244353;
//const int x[4] = {0, -1, 0, 1};
int n;
int c[mxn + 1];
ll dp[mxn + 1][2][2];
vt<int>adj[mxn + 1];
void dfs(int s, int pre){
    vt<ll>comp0, comp1;
    ll sm0 = 0, sm1 = 0;
    for(auto i: adj[s]){
        if(i != pre){
            dfs(i, s);
            comp0.pb(dp[i][0][1] - dp[i][0][0]);
            comp1.pb(dp[i][1][1] - dp[i][1][0]);
            sm0 += dp[i][0][0]; sm1 += dp[i][1][0];
        }
    }
    sort(comp0.begin(), comp0.end()); sort(comp1.begin(), comp1.end());
    ll mnodd = inf, mneven = 0, pref = 0;
    for(int i = 0; i < sz(comp0); i++){
        pref += comp0[i];
        if((i + 1) & 1)mnodd = min(mnodd, pref);
        else mneven = min(mneven, pref);
    }
    dp[s][c[s]][0] = min(inf, mneven + sm0); dp[s][!c[s]][0] = min(inf, mnodd + sm0);
    mnodd = inf, mneven = 0, pref = 0;
    for(int i = 0; i < sz(comp1); i++){
        pref += comp1[i];
        if((i + 1) & 1)mnodd = min(mnodd, pref);
        else mneven = min(mneven, pref);
    }
    dp[s][c[s]][1] = min(inf, mnodd + 1 + sm1); dp[s][!c[s]][1] = min(inf, mneven + 1 + sm1);
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        adj[u].pb(v); adj[v].pb(u);
    }
    for(int i = 1; i <= n; i++)cin >> c[i];
    dfs(1, -1);
    ll ans = min(dp[1][0][0], dp[1][0][1]);
    if(ans == inf)cout << "impossible";
    else cout << ans;
    return(0);
}

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