Submission #551022

#	Time	Username	Problem	Language	Result	Execution time	Memory
551022		ivan24	The Xana coup (BOI21_xanadu)	C++14	0 / 100	117 ms	18164 KiB

xanadu

#include <bits/stdc++.h>

using namespace std;
using ll = long long int;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define F first
#define S second

ll min(ll x, ll y){
    return ((x < y) ? x : y);
}

ll max (ll x, ll y){
    return ((x > y) ? x : y);
}

ll n;
vvi adjList;
vi on,p;
ll dp[2][2][100000];
const ll INF = 1e9;
// dp[works][isOn][node]

void dfs (ll v){
    for (auto u: adjList[v]){
        if (p[v] == u) continue;
        dfs(u);
    }
    for (ll isOn = 0; 2 > isOn; isOn++){
        ll ctr = 0, sum = 0;
        bool bawal = false;
        for (auto u: adjList[v]){
            if (p[v] == u) continue;
            if (dp[1-isOn][0][u] != INF){
                sum += dp[1-isOn][0][u];
            }else if (dp[1-isOn][1][u] != INF){
                sum += dp[1-isOn][1][u];
                ctr++;
            }else if (dp[1-isOn][1][u] == INF && dp[1-isOn][0][u] == INF){
                bawal = true;
                //cout << u << endl;
            }else{
                throw("lol\n");
            }
        }
        if (bawal) continue;
        ctr %= 2;
        ll works = (ctr+on[v]+isOn)%2;
        dp[works][isOn][v] = sum+isOn;
    }
}

void set_p(ll v){
    for (auto u: adjList[v]){
        if (p[v] == u) continue;
        p[u] = v; set_p(u);
    }
    for (ll i = 0; 4 > i; i++)
        dp[i/2][i%2][v] = INF;
}

int main(){
    cin >> n;
    adjList.resize(n);
    for (ll i = 0; n-1 > i; i++){
        ll u,v; cin >> u >> v;
        u--; v--;
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }
    on.resize(n);
    for (auto &i: on){
        cin >> i; i = 1-i;
    }
    p.assign(n,-1);
    set_p(0);
    dfs(0);
    /*
    for (ll v = 0; n > v; v++){
        for (ll i = 0; 2 > i; i++){
            for (ll j = 0; 2 > j; j++) cout << dp[i][j][v] << " ";
        }
        cout << "\n";
    }
    */
    ll res = min(dp[1][1][0], dp[1][0][0]);
    if (res == INF) cout << "impossible\n";
    else cout << res << "\n";
}

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