Submission #498504

#	Time	Username	Problem	Language	Result	Execution time	Memory
498504		Mahfel	The Xana coup (BOI21_xanadu)	C++17	100 / 100	90 ms	27460 KiB

xanadu

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MXN = 1e5 + 20 , Inf = 1e12 + 20;
ll n , color[MXN] , c[MXN];
ll dp[MXN][2][2];
vector<int> adj[MXN];

void DFS(int v , int dad) {
    if(adj[v].size() == 1) {
        for(int i = 0 ; i < 2 ; i++) for(int j = 0 ; j < 2 ; j++) {
            dp[v][i][j] = (i^j ? j : Inf);
        }
        return;
    }
    for(auto u : adj[v]) {
        if(u == dad) continue;
        DFS(u , v);
    }

    for(int i = 0 ; i < 2 ; i++) for(int j = 0 ; j < 2 ; j++) {   // i: color /  j: bezanim ya na

        for(auto u : adj[v]) {
            if(u == dad) continue;
            c[u] = color[u] ^ j;
        }
        ll cst = 0;
        vector<ll> a;
        for(auto u : adj[v]) if(u != dad) {
            a.push_back(dp[u][c[u]][1] - dp[u][c[u]][0]);
            cst += dp[u][c[u]][0];
        }
        sort(a.begin() , a.end());
        ll mn = Inf;
        if(i^j) {
            ll p = 0; mn = 0;
            for(int i = 1 ; i < a.size() ; i+=2) {
                p += a[i]+a[i-1];
                mn = min(mn , p);
            }
        } else {
            ll p = a[0]; mn = min(mn , p);
            for(int i = 2 ; i < a.size() ; i+=2) {
                p += a[i]+a[i-1];
                mn = min(mn , p);
            }            
        }
        dp[v][i][j] = cst + mn + j;
    }

}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n;
    for(int i = 1 ; i < n ; i++) {
        int v,u; cin >> v >> u;
        adj[v].push_back(u); adj[u].push_back(v);
    }
    for(int i = 1 ; i <= n ; i++) {
        cin >> color[i]; color[i] ^= 1;
    }
    int root;
    for(int i = 1 ; i <= n ; i++) if(adj[i].size() > 1) root = i;

    DFS(root , -1);
    ll ans = min(dp[root][color[root]][0] , dp[root][color[root]][1]);
    if(ans > n+1000) {
        cout << "impossible\n";
    } else {
        cout << ans << "\n";
    }
    // for(int i = 1 ; i <= n ; i++) {
    //     for(int a = 0 ; a < 2 ; a++) for(int b = 0 ; b < 2 ; b++) {
    //         cout << dp[i][a][b] << " ";
    //     }
    //     cout << "\n";
    // }
}

Compilation message (stderr)

xanadu.cpp: In function 'void DFS(int, int)':
xanadu.cpp:37:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             for(int i = 1 ; i < a.size() ; i+=2) {
      |                             ~~^~~~~~~~~~
xanadu.cpp:43:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             for(int i = 2 ; i < a.size() ; i+=2) {
      |                             ~~^~~~~~~~~~

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