Submission #1002273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002273		MarwenElarbi	The Xana coup (BOI21_xanadu)	C++17	100 / 100	89 ms	18516 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int MAXN=1e5+5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll dp[MAXN][2][2];
vector<int> tab(MAXN);
vector<int> adj[MAXN];
void dfs(int x,int p){
  for (int i = 0; i < 2; ++i)
  {
    dp[x][i][tab[x]^i]=i;
    dp[x][i][tab[x]^i^1]=1e9;
  }
  for(auto u:adj[x]){
    if(u==p) continue;
    dfs(u,x);
    for (int i = 0; i < 2; ++i)
    {
      ll cur1=dp[x][i][0];
      ll cur2=dp[x][i][1];
      dp[x][i][0]=min(1ll*1000000000,min(cur1+dp[u][0][i],cur2+dp[u][1][i]));
      dp[x][i][1]=min(1ll*1000000000,min(cur2+dp[u][0][i],cur1+dp[u][1][i]));
    }
  }
  //cout <<x<<" "<<dp[x][0][0]<<" "<<dp[x][0][1]<<" "<<dp[x][1][0]<<" "<<dp[x][1][1]<<endl;
  return;
}
int main(){
    int n;
    cin>>n;
    for (int i = 0; i < n-1; ++i)
    {
      int x,y;
      cin>>x>>y;
      x--;y--;
      adj[x].pb(y);
      adj[y].pb(x);
    }
    for (int i = 0; i < n; ++i)
    {
      cin>>tab[i];
    }
    dfs(0,-1);
    if(min(dp[0][0][0],dp[0][1][0])>=1e9) cout <<"impossible"<<endl;
    else cout <<min(dp[0][0][0],dp[0][1][0])<<endl;
}

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