Submission #366692

#	Time	Username	Problem	Language	Result	Execution time	Memory
366692		Mamnoon_Siam	Cats or Dogs (JOI18_catdog)	C++17	38 / 100	3083 ms	7768 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

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

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

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

void solve(int u, int dad = 0) {
  for(int v : g[u]) if(v != dad) {
    solve(v, u);
  }
  dp[u][0] = dp[u][1] = dp[u][2] = inf;
  dp[u][state[u]] = 0;
  for(int v : g[u]) if(v != dad) {
    vi me(dp[u], dp[u]+3), ch(dp[v], dp[v]+3);
    dp[u][0] = dp[u][1] = dp[u][2] = inf;
    for(int i : {0,1,2}) {
      for(int j : {0,1,2}) {
        chkmin(dp[u][i], me[i] + ch[j] + 1);
        if((i|j) != 3) {
          chkmin(dp[u][i|j], me[i] + ch[j]);
        }
      }
    }
  }
}

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(dp[1], dp[1]+3);
}

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

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

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