Submission #283910

#	Time	Username	Problem	Language	Result	Execution time	Memory
283910		rama_pang	Cats or Dogs (JOI18_catdog)	C++14	38 / 100	3082 ms	7400 KiB

catdog

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

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

int N;
vector<int> adj[MAXN];

int dp[MAXN][3];
int state[MAXN];

void DfsInit(int u, int p) {
  if (p) {
    adj[u].erase(find(begin(adj[u]), end(adj[u]), p));
  }
  for (auto v : adj[u]) {
    DfsInit(v, u);
  }
}

void DfsDp(int u) {
  dp[u][0] = dp[u][1] = dp[u][2] = 0;
  for (auto v : adj[u]) {
    DfsDp(v); 
    dp[u][0] += min({dp[v][0], dp[v][1] + 1, dp[v][2] + 1});
    dp[u][1] += min({dp[v][0], dp[v][1] + 0, dp[v][2] + 1});
    dp[u][2] += min({dp[v][0], dp[v][1] + 1, dp[v][2] + 0});
  }
  if (state[u] != 0) {
    dp[u][state[u]] = min(dp[u][state[u]], dp[u][0]);
    dp[u][0] = dp[u][state[u] ^ 3] = INF;
  }
}

int Solve() {
  DfsDp(1);
  return min({dp[1][0], dp[1][1], dp[1][2]});
}

void initialize(int N, vector<int> A, vector<int> B) {
  ::N = N;
  for (int i = 0; i + 1 < N; i++) {
    adj[A[i]].emplace_back(B[i]);
    adj[B[i]].emplace_back(A[i]);
  }
  DfsInit(1, 0);
}

int cat(int v) {
  state[v] = 1;
  return Solve();
}

int dog(int v) {
  state[v] = 2;
  return Solve();
}

int neighbor(int v) {
  state[v] = 0;
  return Solve();
}

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