Submission #1100988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100988		epicci23	The Xana coup (BOI21_xanadu)	C++17	100 / 100	69 ms	15864 KiB

xanadu

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 1e5 + 5;
const int INF = 1e10;
vector<int> v[N];
int dp[N][2][2],col[N],n;

void dfs(int c,int p){
  for(int x:v[c]){
    if(x==p) continue;
    dfs(x,c);
  }
  // bas
  int hm=0,lol=0,mini=INF;
  bool patladik=0;
  for(int x:v[c]){
  	if(x==p) continue;
    if(dp[x][1][0]==INF && dp[x][1][1]==INF){
      patladik=1;
      break;
    }
    hm+=min(dp[x][1][0],dp[x][1][1]);
    if(dp[x][1][1]<dp[x][1][0]) lol^=1;
    if(dp[x][1][1]!=INF && dp[x][1][0]!=INF) 
      mini=min(mini,abs(dp[x][1][1]-dp[x][1][0]));
  }

  if(patladik) dp[c][1][1]=dp[c][0][1]=INF;
  else{
   dp[c][lol^col[c]^1][1]=hm+1;
   if(mini==INF) dp[c][lol^col[c]][1]=INF;
   else dp[c][lol^col[c]][1]=hm+1+mini;
  }
  
  // basma

  hm=0,lol=0,mini=INF;
  patladik=0;
  for(int x:v[c]){
  	if(x==p) continue;
    if(dp[x][0][0]==INF && dp[x][0][1]==INF){
      patladik=1;
      break;
    }
    hm+=min(dp[x][0][0],dp[x][0][1]);
    if(dp[x][0][1]<dp[x][0][0]) lol^=1;
    if(dp[x][0][1]!=INF && dp[x][0][0]!=INF) 
      mini=min(mini,abs(dp[x][0][1]-dp[x][0][0]));
  }

  if(patladik) dp[c][0][0]=dp[c][1][0]=INF;
  else{
   dp[c][lol^col[c]][0]=hm;
   if(mini==INF) dp[c][lol^col[c]^1][0]=INF;
   else dp[c][lol^col[c]^1][0]=hm+mini;
  }
}

void _(){
  for(int i=0;i<N;i++){
  	for(int j=0;j<2;j++){
  	  for(int z=0;z<2;z++)
  	  	dp[i][j][z]=INF;
  	}
  }
  cin >> n;
  for(int i=1;i<n;i++){
  	int a,b;
  	cin >> a >> b;
  	v[a].push_back(b);
  	v[b].push_back(a);
  }
  for(int i=1;i<=n;i++) cin >> col[i];
  dfs(1,1);

  if(min(dp[1][0][1],dp[1][0][0])==INF) cout << "impossible\n";
  else cout << min(dp[1][0][1],dp[1][0][0]) << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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