Submission #977289

#	Time	Username	Problem	Language	Result	Execution time	Memory
977289		underwaterkillerwhale	The Xana coup (BOI21_xanadu)	C++17	100 / 100	60 ms	28752 KiB

xanadu

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 3e5 + 7;
const ll Mod = 1e9 + 7;
const int szBL = 916;
const ll INF = 1e12;
const int BASE = 137;

int n, Q;
int a[N];
ll dp[N][2][2];
vector<int> ke[N];

void dfs (int u, int p) {
    iter (&v, ke[u]) {
        if (v == p) continue;
        dfs (v, u);
//        rep (i, 0, 1) rep (j, 0, 1) cout<<v<<","<<i<<","<<j<<": "<<dp[v][i][j] <<"\n";
    }
    if (SZ(ke[u]) == 1 && p != 0) {
        dp[u][a[u]][0] = 0;
        dp[u][a[u] ^ 1][1] = 1;
        return;
    }
    static vector<ll> vec; vector<ll> ().swap(vec);
    ll tot = 0;
    iter(&v, ke[u]) if (v != p) {
        tot += dp[v][0][0];
        if (dp[v][0][1] < INF) vec.push_back(-dp[v][0][0] + dp[v][0][1]);
        else vec.push_back(INF);
    }
    sort (ALL(vec));
    dp[u][a[u]][0] = min(dp[u][a[u]][0], tot);
    rep (i, 0, SZ(vec) - 1) {
        tot += vec[i];
        if ((i + 1) % 2 == a[u]) dp[u][0][0] = min (dp[u][0][0], tot);
        else dp[u][1][0] = min(dp[u][1][0], tot);
    }
    tot = 0;
    vector<ll> ().swap(vec);
    iter(&v, ke[u]) if (v != p) {
        tot += dp[v][1][0];
        if (dp[v][1][1] < INF) vec.push_back(-dp[v][1][0] + dp[v][1][1]);
        else vec.push_back(INF);
    }
    dp[u][a[u] ^ 1][1] = min(dp[u][a[u] ^ 1][1], tot + 1);
//    if (u == 3) cout << SZ(vec) <<" hi\n";
    sort (ALL(vec));
    rep (i, 0, SZ(vec) - 1) {
        tot += vec[i];
        if ((i + 1) % 2 == a[u]) dp[u][1][1] = min(dp[u][1][1], tot + 1);
        else {
            dp[u][0][1] = min(dp[u][0][1], tot + 1);
//            if (u == 1)    cout << dp[u][0][1] <<" hji\n";
        }
    }
}

void solution() {
    cin >> n;
    rep (i, 1, n - 1 ) {
        int u, v;
        cin >> u >> v;
        ke[u].push_back(v);
        ke[v].push_back(u);
    }
    rep (i, 1, n) {
        cin >> a[i];
    }
    rep (i, 1, n) rep (j, 0, 1) rep (k, 0, 1) dp[i][j][k] = INF;
    dfs(1, 0);
    ll res = min(dp[1][0][1], dp[1][0][0]);
    if (res < INF) cout << res <<"\n";
    else  cout <<"impossible\n";
}



#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);

int main () {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
18 3
2 5
6 21
13 19
9 17
14 17
19 20
2 16
2 10
9 14
19 20
14 16
1 3
17 19
14 21
18 19
4 7
5 12
1 13

*/

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