Submission #284325

#	Time	Username	Problem	Language	Result	Execution time	Memory
284325		rama_pang	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	275 ms	18168 KiB

catdog

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

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

class Node {
 public:
  int par, ch[2], state;
  int sum[2]; // sum of dp of light children
  int dp[2][2];  // merged values on chain (dp[i][j] = start from color i, ending at color j)
  
  Node() {
    par = ch[0] = ch[1] = 0;
    state = 2;
    sum[0] = sum[1] = 0;
    dp[0][0] = 0; dp[0][1] = INF;
    dp[1][0] = INF; dp[1][1] = 0;
  }

  void ChangeState(int t) {
    state = t;
  }

  int Answer() {
    return min({dp[0][0], dp[0][1], dp[1][0], dp[1][1]});
  }
};

int root;
Node tree[MAXN];

int sub[MAXN];
int heavy[MAXN];
vector<int> adj[MAXN];

bool IsChainRoot(int u) {
  return tree[tree[u].par].ch[0] != u && tree[tree[u].par].ch[1] != u;
}

void Reupdate(int u) {                                                // array<int, 2>{1, 0}});
  tree[u].dp[0][0] = tree[u].sum[0]; tree[u].dp[0][1] = INF;
  tree[u].dp[1][0] = INF; tree[u].dp[1][1] = tree[u].sum[1];

  if (tree[u].state == 0) {
    tree[u].dp[0][0] = INF;
  } else if (tree[u].state == 1) {
    tree[u].dp[1][1] = INF;
  }

  static int res[2][2];

  if (tree[u].ch[1]) {
    res[0][0] = res[0][1] = res[1][0] = res[1][1] = INF;
    int oth = tree[u].ch[1];
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        for (int k = 0; k < 2; k++) {
          for (int l = 0; l < 2; l++) {
            res[i][j] = min(res[i][j], (k != l) + tree[u].dp[i][k] + tree[oth].dp[l][j]);
          }
        }
      }
    }
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        tree[u].dp[i][j] = res[i][j];
      }
    }
  }

  if (tree[u].ch[0]) {
    res[0][0] = res[0][1] = res[1][0] = res[1][1] = INF;
    int oth = tree[u].ch[0];
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        for (int k = 0; k < 2; k++) {
          for (int l = 0; l < 2; l++) {
            res[i][j] = min(res[i][j], (k != l) + tree[oth].dp[i][k] + tree[u].dp[l][j]);
          }
        }
      }
    }
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        tree[u].dp[i][j] = res[i][j];
      }
    }
  }
}

void UpdateSum(int p, int u, int sgn) {
  tree[p].sum[0] += sgn * min({tree[u].dp[0][0], tree[u].dp[0][1], 
                               tree[u].dp[1][0] + 1, tree[u].dp[1][1] + 1});
  tree[p].sum[1] += sgn * min({tree[u].dp[1][0], tree[u].dp[1][1], 
                               tree[u].dp[0][0] + 1, tree[u].dp[0][1] + 1});
}

int Update(int u, int type) {
  tree[u].ChangeState(type);
  for (; u; u = tree[u].par) {
    if (tree[u].par && IsChainRoot(u)) {
      UpdateSum(tree[u].par, u, -1);
      Reupdate(u);
      UpdateSum(tree[u].par, u, +1);
    } else {
      Reupdate(u);
    }
  }
  return tree[root].Answer();
}

void DfsInit(int u, int p) {
  if (p) {
    adj[u].erase(find(begin(adj[u]), end(adj[u]), p));
  }
  sub[u] = 1;
  for (auto &v : adj[u]) {
    DfsInit(v, u);
    sub[u] += sub[v];
    if (!heavy[u] || sub[heavy[u]] < sub[v]) {
      heavy[u] = v;
    }
  }
}

int Build(int l, int r, const vector<int> &chain) {
  if (l > r) return 0;
  int all = 0, cur = 0, mid;
  for (int i = l; i <= r; i++) all += sub[chain[i]];
  for (mid = l; mid <= r; mid++) {
    cur += sub[chain[mid]];
    if (cur * 2 > all) {
      break;
    }
  }
  int id = chain[mid];
  tree[id].ch[0] = Build(l, mid - 1, chain);
  tree[id].ch[1] = Build(mid + 1, r, chain);
  if (tree[id].ch[0]) tree[tree[id].ch[0]].par = id;
  if (tree[id].ch[1]) tree[tree[id].ch[1]].par = id;
  Reupdate(id);
  return id;
}

int Construct(int u) {
  for (int i = u; i; i = heavy[i]) {
    for (auto v : adj[i]) {
      if (v != heavy[i]) {
        int r = Construct(v);
        tree[r].par = i;
        UpdateSum(i, r, +1);
      }
    }
  }
  static vector<int> chain; chain.clear();
  for (int i = u; i; i = heavy[i]) {
    chain.emplace_back(i);
  }
  for (int i = 0; i + 1 < (int) chain.size(); i++) {
    sub[chain[i]] -= sub[chain[i + 1]];
  }
  return Build(0, int(chain.size()) - 1, chain);
}

void initialize(int N, vector<int> A, vector<int> B) {
  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);
  root = Construct(1);
}

int cat(int v) {
  return Update(v, 0);
}

int dog(int v) {
  return Update(v, 1);
}

int neighbor(int v) {
  return Update(v, 2);
}

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