Submission #379508

#	Time	Username	Problem	Language	Result	Execution time	Memory
379508		qwerty234	Cats or Dogs (JOI18_catdog)	C++14	38 / 100	3059 ms	9948 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back

using namespace std;

const int MAXN = 2e5 + 10;

int dp[MAXN][3], col[MAXN], inf = 1e9;
vector <int> g[MAXN];

void initialize(int n, vector <int> a, vector <int> b) {
  for (int i = 1; i <= n; i++)
    g[i].clear();
  for (int i = 0; i < n - 1; i++) {
    g[a[i]].pb(b[i]);
    g[b[i]].pb(a[i]);
  }
  for (int i = 1; i <= n; i++)
    col[i] = 0;
}

void dfs(int u, int p) {
  for (int to : g[u]) {
    if (p == to)
      continue;
    dfs(to, u);
  }
  if (col[u] == 0) {
    dp[u][0] = dp[u][1] = dp[u][2] = 0;
    for (int to : g[u]) {
      if (to == p)
        continue;
      dp[u][0] += min(min(inf, dp[to][0]), min(dp[to][1] + 1, dp[to][2] + 1));
      dp[u][1] += min(min(inf, dp[to][0]), min(dp[to][1], dp[to][2] + 1));
      dp[u][2] += min(min(inf, dp[to][0]), min(dp[to][1] + 1, dp[to][2]));
      dp[u][0] = min(dp[u][0], inf);
      dp[u][1] = min(dp[u][1], inf);
      dp[u][2] = min(dp[u][2], inf);
    }
  } else if (col[u] == 1) {
    dp[u][0] = dp[u][2] = inf; dp[u][1] = 0;
    for (int to : g[u]) {
      if (to == p)
        continue;
      dp[u][1] += min(min(inf, dp[to][0]), min(dp[to][1], dp[to][2] + 1));
      dp[u][1] = min(dp[u][1], inf);
    }
  } else {
    dp[u][0] = dp[u][1] = inf; dp[u][2] = 0;
    for (int to : g[u]) {
      if (to == p)
        continue;
      dp[u][2] += min(min(inf, dp[to][0]), min(dp[to][1] + 1, dp[to][2]));
      dp[u][2] = min(dp[u][2], inf);
    }
  }
}

int cat(int v) {
  col[v] = 1;
  dfs(1, -1);
  return min(dp[1][0], min(dp[1][1], dp[1][2]));
}

int dog(int v) {
  col[v] = 2;
  dfs(1, -1);
  return min(dp[1][0], min(dp[1][1], dp[1][2]));
}

int neighbor(int v) {
  col[v] = 0;
  dfs(1, -1);
  return min(dp[1][0], min(dp[1][1], dp[1][2]));
}

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