Submission #1150496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150496		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];
    g[v].push_back(u);
    g[u].push_back(v);
  }
}
ll calc(){
  ll ans=0;
  for(ll i=1;i<=n;i++){
    if(a[i]==0)continue;
    for(auto to:g[i]){
      if(a[i]+a[to]==0)ans++;
      if(!a[to]){
        if(a[i]==-1)cntc[to]++;
        else cntd[to]++;
      }
    }
  }ans/=2;
  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) {
  a[v]=0;
  return calc();
}

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