Submission #924316

#	Time	Username	Problem	Language	Result	Execution time	Memory
924316		TahirAliyev	The Xana coup (BOI21_xanadu)	C++17	10 / 100	97 ms	35628 KiB

xanadu

#include <bits/stdc++.h>

#define ll long long
using namespace std;
#define pii pair<ll, ll>
ll oo = 1e18 + 9;
int n, m, k;
const int MAX = 2e5 + 5, MOD = 1e9 + 7, LOGMAX = 25;

vector<int> g[MAX];
int col[MAX];

ll dp[MAX][2][2];

void dfs(int node, int p){
    dp[node][0][0] = oo;
    dp[node][0][1] = oo;
    dp[node][1][0] = oo;
    dp[node][1][1] = oo;

    ll sum = 0, sum2 = 0;
    vector<ll> s, s2;
    int cnt = 0, cnt2 = 0;
    for(int to : g[node]){
        if(p == to) continue;
        dfs(to, node);
        if(dp[to][0][1] > MAX && dp[to][0][0] > MAX){
            sum = oo;
        }
        else{
            sum += dp[to][0][0];
            s.push_back(dp[to][0][1] - dp[to][0][0]);
        }
        if(dp[to][0][1] < MAX){
            cnt++;
        }
        if(dp[to][1][1] > MAX && dp[to][1][0] > MAX){
            sum2 = oo;
        }
        else{
            sum2 += dp[to][1][0];
            s2.push_back(dp[to][1][1] - dp[to][1][0]);
        }
        if(dp[to][1][1] < MAX){
            cnt2++;
        }
    }
    sort(s.begin(), s.end());
    sort(s2.begin(), s2.end());
    s.insert(s.begin(), 0);
    s2.insert(s2.begin(), 0);
    ll pre = 0;
    for(int i = 0; i < s.size(); i++){
        pre += s[i];
        if(i < cnt) continue;
        if(i & 1){
            dp[node][0][0] = min(sum + pre, dp[node][0][0]);
        }
        else{
            dp[node][1][0] = min(sum + pre, dp[node][1][0]);
        }
    }
    pre = 0;
    for(int i = 0; i < s2.size(); i++){
        pre += s2[i];
        if(i < cnt2) continue;
        if(i & 1){
            dp[node][1][1] = min(sum2 + pre, dp[node][1][1]);
        }
        else{
            dp[node][0][1] = min(sum2 + pre, dp[node][0][1]); 
        }
    }
    dp[node][1][1]++;
    dp[node][0][1]++;
    if(!col[node]){
        swap(dp[node][0][0], dp[node][1][0]);
        swap(dp[node][0][1], dp[node][1][1]);
    }
}

void solve(){
    cin >> n;
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 1; i <= n; i++) cin >> col[i];
    dfs(1, 1);
    if(min(dp[1][0][0], dp[1][0][1]) >= MAX){
        cout << "impossible\n";
    }
    else{
        cout << min(dp[1][0][0], dp[1][0][1]) << '\n';
    }
}

signed main(){
    int t = 1;
    for(int i = 1; i <= t; i++){
        solve();
    }
}

Compilation message (stderr)

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

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