oj.uz

Submission #883995

# Submission time Handle Problem Language Result Execution time Memory
883995 2023-12-06T14:01:30 Z vjudge1 Cats or Dogs (JOI18_catdog) C++17
8 / 100
 21 ms 3420 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3292 KB Output is correct
3 Correct 4 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 19 ms 3392 KB Output is correct
7 Correct 11 ms 3164 KB Output is correct
8 Correct 13 ms 3392 KB Output is correct
9 Correct 21 ms 3160 KB Output is correct
10 Correct 12 ms 3160 KB Output is correct
11 Correct 9 ms 3392 KB Output is correct
12 Correct 1 ms 3164 KB Output is correct
13 Correct 1 ms 3164 KB Output is correct
14 Correct 1 ms 3400 KB Output is correct
15 Correct 1 ms 3164 KB Output is correct
16 Correct 18 ms 3164 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3292 KB Output is correct
3 Correct 4 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 19 ms 3392 KB Output is correct
7 Correct 11 ms 3164 KB Output is correct
8 Correct 13 ms 3392 KB Output is correct
9 Correct 21 ms 3160 KB Output is correct
10 Correct 12 ms 3160 KB Output is correct
11 Correct 9 ms 3392 KB Output is correct
12 Correct 1 ms 3164 KB Output is correct
13 Correct 1 ms 3164 KB Output is correct
14 Correct 1 ms 3400 KB Output is correct
15 Correct 1 ms 3164 KB Output is correct
16 Correct 18 ms 3164 KB Output is correct
17 Incorrect 2 ms 3420 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3292 KB Output is correct
3 Correct 4 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 19 ms 3392 KB Output is correct
7 Correct 11 ms 3164 KB Output is correct
8 Correct 13 ms 3392 KB Output is correct
9 Correct 21 ms 3160 KB Output is correct
10 Correct 12 ms 3160 KB Output is correct
11 Correct 9 ms 3392 KB Output is correct
12 Correct 1 ms 3164 KB Output is correct
13 Correct 1 ms 3164 KB Output is correct
14 Correct 1 ms 3400 KB Output is correct
15 Correct 1 ms 3164 KB Output is correct
16 Correct 18 ms 3164 KB Output is correct
17 Incorrect 2 ms 3420 KB Output isn't correct
18 Halted 0 ms 0 KB -