제출 #1150506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150506		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;
vector<ll>g[N];

void initialize(int N, std::vector<int> A, std::vector<int> B) {
  m=A.size();
  n=N;
  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(){
  ll ans=0;
  for(ll i=1;i<=n;i++)cntc[i]=cntd[i]=0;
  for(ll i=1;i<=n;i++){
    if(a[i]==0)continue;
    for(auto to:g[i]){
      if(a[to]==1&&a[i]==-1)ans++;
      if(!a[to]){
        if(a[i]==-1)cntc[to]++;
        else cntd[to]++;
      }
    }
  }
  for(ll i=1;i<=n;i++){
    if(a[i])continue;
    ans+=min(cntc[i],cntd[i]);
 
  }return ans;
}
int cat(int v) {
  a[v]=1;
  return calc();
}

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

int neighbor(int v) {
  ll x=a[v];
  a[v]=0;
  ll pos=0,ans=1e18;
  for(ll to:g[v]){
    a[to]=x;
    
  }
  return calc();
}

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