Submission #551348

#	Time	Username	Problem	Language	Result	Execution time	Memory
551348		ivan24	The Xana coup (BOI21_xanadu)	C++14	100 / 100	170 ms	29044 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;
        vi diff;
        for (auto u: adjList[v]){
            if (p[v] == u) continue;
            if (dp[1-isOn][0][u] != INF && dp[1-isOn][1][u] == INF){
                sum += dp[1-isOn][0][u];
            }else if (dp[1-isOn][1][u] != INF && dp[1-isOn][0][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{
                sum += dp[1-isOn][0][u];
                diff.push_back(dp[1-isOn][1][u]-dp[1-isOn][0][u]);
            }
        }
        if (bawal) continue;
        ctr %= 2;
        ll works = (ctr+on[v]+isOn)%2;
        dp[works][isOn][v] = min(sum+isOn,dp[works][isOn][v]);
        if (!diff.empty()){
            sort(diff.begin(),diff.end());
            for (ll i = 0; diff.size() > i; i++){
                works++; works %= 2;
                sum += diff[i];
                dp[works][isOn][v] = min(sum+isOn,dp[works][isOn][v]);
            }
        }

    }
}

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";
}

Compilation message (stderr)

xanadu.cpp: In function 'void dfs(ll)':
xanadu.cpp:58:40: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   58 |             for (ll i = 0; diff.size() > i; i++){
      |                            ~~~~~~~~~~~~^~~

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