Submission #655266

#	Time	Username	Problem	Language	Result	Execution time	Memory
655266		600Mihnea	The Xana coup (BOI21_xanadu)	C++17	100 / 100	83 ms	23172 KiB

xanadu

#include <bits/stdc++.h>

using namespace std;

const int N=(int)1e5+7;
const int INF=(int)1e9+7;
int n;
int v[N];
int cost[N][2][2];
int nw[2][2];
vector<int> g[N];

void minup(int &a,int b){
        a=min(a,b);
}

void dfs(int a,int p=-1){
        vector<int> kids;
        for (auto &b : g[a]){
                if (b==p){
                        continue;
                }
                kids.push_back(b);
                dfs(b,a);
        }
        g[a]=kids;
        cost[a][0][0]=cost[a][0][1]=cost[a][1][0]=cost[a][1][1]=INF;
        cost[a][0][v[a]]=0;
        cost[a][1][v[a]^1]=1;


        for (auto &b : g[a]){
                nw[0][0]=nw[0][1]=nw[1][0]=nw[1][1]=INF;
                for (int apply=0;apply<=1;apply++){
                        for(int cur=0;cur<=1;cur++){
                                for (int apply_b=0;apply_b<=1;apply_b++){
                                        for (int cur_b=0;cur_b<=1;cur_b++){
                                                if ((cur_b^apply)==0){
                                                        minup(nw[apply][cur^apply_b],cost[a][apply][cur]+cost[b][apply_b][cur_b]);
                                                }
                                        }
                                }
                        }
                }
                for(int i=0;i<=1;i++){
                        for (int j=0;j<=1;j++){
                                cost[a][i][j]=nw[i][j];
                        }
                }
        }
}

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

        ///freopen("___input___.txt","r",stdin);

        cin>>n;
        for (int i=1;i<n;i++){
                int a,b;
                cin>>a>>b;
                g[a].push_back(b);
                g[b].push_back(a);
        }
        for (int i=1;i<=n;i++){
                cin>>v[i];
        }
        dfs(1);
        int sol=INF;
        for (int x=0;x<=1;x++){
                sol=min(sol,cost[1][x][0]);
        }
        if(sol==INF){
                cout<<"impossible\n";
                return 0;
        }
        cout<<sol<<"\n";
        return 0;
}

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