Submission #1001973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001973		MarwenElarbi	The Xana coup (BOI21_xanadu)	C++17	0 / 100	72 ms	17920 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());
int dp[MAXN][2];
vector<int> tab(MAXN);
vector<int> adj[MAXN];
bool toggle[MAXN][2];
void dfs(int x,int p){
  if(adj[x].size()==1&&p!=-1){
    if(tab[x]==1){
      dp[x][1]=0;
      dp[x][0]=1;
      toggle[x][1]=0;
      toggle[x][0]=1;
    }else{
      dp[x][0]=0;
      dp[x][1]=1;
      toggle[x][0]=0;
      toggle[x][1]=1;
    }
    return;
  }
  toggle[x][1]=1^tab[x];
  toggle[x][0]=tab[x];
  int one=0;
  int zero=0;
  for(auto u:adj[x]){
    if(u==p) continue;
    dfs(u,x);
    one+=dp[u][1];
    zero+=dp[u][0];
    toggle[x][0]^=toggle[u][0];
    toggle[x][1]^=toggle[u][1];
  }
  if(toggle[x][0]){
    dp[x][1]=zero;
  }else dp[x][0]=zero;
  if(toggle[x][1]){
    dp[x][1]=min(one+1,dp[x][1]);
  }else dp[x][0]=min(dp[x][0],one+1);
  toggle[x][1]=1^tab[x];
  toggle[x][0]=tab[x];
  //cout <<x<<" "<<dp[x][0]<<" "<<dp[x][1]<<endl;
  return;
}
int main(){
    int n;
    cin>>n;
    for (int i = 0; i < n; ++i)
    {
      dp[i][0]=dp[i][1]=1e9;
    }
    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(dp[0][0]>=1e9) cout <<"impossible"<<endl;
    else cout <<dp[0][0]<<endl;
}

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