Submission #883995

#	Time	Username	Problem	Language	Result	Execution time	Memory
883995		vjudge1	Cats or Dogs (JOI18_catdog)	C++17	8 / 100	21 ms	3420 KiB

catdog

#include <bits/stdc++.h>

#include "catdog.h"

#define fi first
#define se second

#define bit(mask, i) (((mask) >> (i)) & 1)

using namespace std;

using ll = long long;
using pii = pair<int, int>;

const int NMAX = 1e5+5;
const int INF = 1e9+5;

int n;
vector<pii> g[NMAX];
int a[NMAX], daddy[NMAX];

void initialize(int N, std::vector<int> A, std::vector<int> B) {
   n = N;
   for (int i = 0; i < n - 1; i++) {
      g[A[i]].push_back({ B[i], i });
      g[B[i]].push_back({ A[i], i });
   }
}

bool check(int mask) {
   int vis = 0;
   function<bool(int, int)> dfs = [&](int x, int t) {
      if (a[x] != t && a[x]) return false;
      vis |= 1 << x;
      for (auto &u : g[x]) {
         if (!bit(mask, u.se) && !bit(vis, u.fi)) {
            if (!dfs(u.fi, t))
               return false;
         }
      }
      return true;
   };
   for (int i = 1; i <= n; i++) {
      if (a[i] && !bit(vis, i) && !dfs(i, a[i]))
         return false;
   }
   return true;
}

int calc() {
   int ret = INF;
   for (int mask = 0; mask < 1 << (n - 1); mask++) {
      if (__builtin_popcount(mask) >= ret)
         continue;
      if (check(mask))
         ret = __builtin_popcount(mask);
   }
   return ret;
}

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

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

int neighbor(int v) {
   a[v] = 0;
   return calc();
}

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