Submission #1150499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150499		brover29	Cats or Dogs (JOI18_catdog)	C++20	0 / 100	1 ms	2628 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++){
    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]);
    cntc[i]=0;
    cntd[i]=0;
  }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