Submission #1150533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150533		brover29	Cats or Dogs (JOI18_catdog)	C++20	0 / 100	1 ms	2624 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N=1e5+29;
ll n,a[N],cntc[N],cntd[N],m,dp[N][8],dp2[8],cnt[N][4];
vector<ll>g[N];
bool can(ll v,ll mask){
  if(a[v]==4)return 1;
  if((mask>>(3^a[v]))&1)return 1;
  return 0;
}
void merge(ll v,ll u){
  if((a[v]^a[u])==3){
    for(ll mask=1;mask<=7;mask++){
      dp2[mask]=1e18;
      if(!((mask>>a[u])&1))continue;
      dp2[mask]=dp[v][mask]+1+min({dp[u][0],dp[u][1],dp[u][2],dp[u][3],dp[u][4],dp[u][5],dp[u][6],dp[u][7]});
    }
  }else{
    for(ll mask=0;mask<=7;mask++){
      dp2[mask]=1e18;
      if(can(v,mask)){
        dp2[mask]=dp[v][mask]+1+min({dp[u][0],dp[u][1],dp[u][2],dp[u][3],dp[u][4],dp[u][5],dp[u][6],dp[u][7]});
        if(!((mask>>a[u])&1))dp2[mask]=min(dp2[mask],dp[v][mask]+dp[u][mask]);
      }
    }
  }for(ll mask=0;mask<=7;mask++)dp[v][mask]=dp2[mask];
}void dfs(ll v,ll pr=0){
  for(ll mask=0;mask<=7;mask++){
    dp[v][mask]=0;
  }for(ll to:g[v]){
    if(to==pr)continue;
    dfs(to,v);
    merge(v,to);
  }
}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
  m=A.size();
  n=N;
  for(ll i=1;i<=n;i++)a[i]=4;
  for(ll i=0;i<m;i++){
    ll u=A[i];
    ll v=B[i];
    assert(u>0&&u<=n);
    assert(v>0&&v<=n);
    g[v].push_back(u);  
    g[u].push_back(v);
  }
}
ll calc(){
  dfs(1);
  return min({dp[1][0],dp[1][1],dp[1][2],dp[1][3],dp[1][4],dp[1][5],dp[1][6],dp[1][7]});
}
int cat(int v) {
  a[v]=1;
  return calc();
}

int dog(int v) {
  a[v]=2;
  return calc();
}

int neighbor(int v) {
  ll x=a[v];
  a[v]=4;
  
  return calc();
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 30
• Subtask 3: 0 / 62