Submission #1218150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218150		sophiaeternalia	The Xana coup (BOI21_xanadu)	C++20	0 / 100	33 ms	18500 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<vector<int>> g;
vector<int> a;
vector<array<int, 4>> dp;

void dfs(int v, int la){
    if (g[v].size()<2 and la!=-1){
        if (a[v]==0){
            dp[v]={1, (int)1e9, (int)1e9, 0};
        } else {
            dp[v]={(int)1e9, 0, 1, (int)1e9};
        }
        return;
    }
    array<int, 4> ar={0, 0, 0, 0};
    for (auto u: g[v]){
        if (u!=la){
            dfs(u, v);
            if (ar[0]==1e9 or dp[u][0]==1e9){
                ar[0]=1e9;
            } else {
                ar[0]+=dp[u][0];
            }
            if (ar[1]==1e9 or dp[u][1]==1e9){
                ar[1]=1e9;
            } else {
                ar[1]+=dp[u][1];
            }
            if (ar[2]==1e9 or dp[u][2]==1e9){
                ar[2]=1e9;
            } else {
                ar[2]+=dp[u][2];
            }
            if (ar[3]==1e9 or dp[u][3]==1e9){
                ar[3]=1e9;
            } else {
                ar[3]+=dp[u][3];
            }
        }
    }
    if (ar[0]!=1e9){
        ar[0]++;
    }
    if (ar[1]!=1e9){
        ar[1]++;
    }
    if (ar[2]!=1e9){
        ar[2]++;
    }
    if (ar[3]!=1e9){
        ar[3]++;
    }
    if (a[v]==1){
        dp[v]={ar[0], ar[3], ar[1], ar[2]};
    } else {
        dp[v]={ar[1], ar[2], ar[0], ar[3]};
    }
    return;
}

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

    int n;
    cin>>n;
    g.resize(n);
    a.resize(n);
    dp.resize(n);
    for (int i=0; i<n-1; i++){
        int a, b;
        cin>>a>>b;
        a--;
        b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i=0; i<n; i++){
        cin>>a[i];
    }
    dfs(0, -1);
    if (dp[0][2]==1e9 and dp[0][3]==1e9){
        cout<<"impossible"<<"\n";
    } else {
        cout<<min(dp[0][2], dp[0][3])<<"\n";
    }
}

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