Submission #366693

#	Time	Username	Problem	Language	Result	Execution time	Memory
366693		Mamnoon_Siam	Cats or Dogs (JOI18_catdog)	C++17	38 / 100	3063 ms	6440 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;

/* sorry, this is the bare minimum :'( */
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second

using tri = array<int, 3>;

const int N = 1e5 + 5;
const int inf = 1e9 + 5;


int n;
int state[N];
tri dp[N];
vi g[N];

void chkmin(int& x, int y) {
  x = min(x, y);
}

tri merge(tri a, tri b) {
  tri ret = {inf, inf, inf};
  for(int i : {0,1,2}) for(int j : {0,1,2}) {
    chkmin(ret[i], a[i]+b[j]+1);
    if((i|j) != 3) chkmin(ret[i|j], a[i]+b[j]);
  }
  return ret;
}

void solve(int u, int dad = 0) {
  for(int v : g[u]) if(v != dad) {
    solve(v, u);
  }
  dp[u] = {inf, inf, inf};
  dp[u][state[u]] = 0;
  for(int v : g[u]) if(v != dad) {
    dp[u] = merge(dp[u], dp[v]);
  }
}

void initialize(int _n, std::vector<int> A, std::vector<int> B) {
  n = _n;
  for(int i = 0; i < sz(A); ++i) {
    g[A[i]].emplace_back(B[i]);
    g[B[i]].emplace_back(A[i]);
  }
}

int cat(int v) {
  state[v] = 1;
  solve(1);
  return *min_element(all(dp[1]));
}

int dog(int v) {
  state[v] = 2;
  solve(1);
  return *min_element(all(dp[1]));
}

int neighbor(int v) {
  state[v] = 0;
  solve(1);
  return *min_element(all(dp[1]));
}

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