제출 #1150538

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150538		brover29	Cats or Dogs (JOI18_catdog)	C++20	38 / 100	3095 ms	7636 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][4];
vector<ll>g[N];

void dfs(ll v,ll pr=0){
 dp[v][2]=dp[v][1]=0;
 dp[v][3^a[v]]=1e9;
 for(ll to:g[v]){
    if(to==pr)continue;
    dfs(to,v);
    dp[v][1]+=min(dp[to][1],dp[to][2]+1);
    dp[v][2]+=min(dp[to][2],dp[to][1]+1);
  }
}
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][1],dp[1][2]);
}
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]=3;
  
  return calc();
}

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