Submission #821788

#	Time	Username	Problem	Language	Result	Execution time	Memory
821788		alvingogo	The Xana coup (BOI21_xanadu)	C++14	100 / 100	62 ms	18860 KiB

xanadu

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

const int inf=1e9;
struct no{
    vector<int> ch;
    int dp[2][2]={inf,inf,inf,inf};
    int t=0;
};
vector<no> v;
void dfs(int r,int f){
    for(auto h:v[r].ch){
        if(h!=f){
            dfs(h,r);
        }
    }
    for(int j=0;j<2;j++){
        int a=0,b=inf;
        for(auto h:v[r].ch){
            if(h!=f){
                int c=min(a+v[h].dp[j][0],b+v[h].dp[j][1]);
                int d=min(a+v[h].dp[j][1],b+v[h].dp[j][0]);
                a=c;
                b=d;
            }
        }
        v[r].dp[v[r].t^j][j]=a+j;
        v[r].dp[v[r].t^j^1][j]=b+j;
    }
}
signed main(){
    AquA;
    int n;
    cin >> n;
    v.resize(n);
    for(int i=1;i<n;i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        v[a].ch.push_back(b);
        v[b].ch.push_back(a);
    }
    for(int i=0;i<n;i++){
        cin >> v[i].t;
    }
    dfs(0,0);
    int mn=min(v[0].dp[0][0],v[0].dp[0][1]);
    if(mn>5e8){
        cout << "impossible" << "\n";
        return 0;
    }
    cout << mn << "\n";
    return 0;
}

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