Submission #1042286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042286		juicy	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	323 ms	27636 KiB

catdog

#include "catdog.h"

#include <bits/stdc++.h>

using namespace std;

template<class T, size_t D>
ostream &operator << (ostream &os, array<T, D> v) {
  os << "{";
  for (int i = 0; i < D; ++i) {
    os << (i ? ", " : "") << v[i];
  }
  return os << "}";
}

void __print() {
  cerr << "]\n";
}

template<class T, class... V>
void __print(T t, V... v) {
  cerr << t;
  if (sizeof...(v)) {
    cerr << ", ";
  }
  __print(v...);
} 

#define debug(x...) cerr << "[" << #x << "] = ["; __print(x);

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

using Node = array<array<int, 2>, 2>;

int n;
int tin[N], head[N], pr[N], sz[N], tail[N], state[N], pos[N];
Node s[4 * N];
array<int, 2> sum[N], up[N];
vector<int> g[N];

Node operator + (const Node &lt, const Node &rt) {
  Node res{array<int, 2>{inf, inf}, array<int, 2>{inf, inf}};
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      if (lt[i][j] != inf) {
        for (int k = 0; k < 2; ++k) {
          for (int l = 0; l < 2; ++l) {
            if (rt[k][l] != inf) {
              res[i][l] = min(res[i][l], lt[i][j] + rt[k][l] + (j ^ k));
            }
          }
        }
      }
    }
  }
  return res;
}

void bld(int id = 1, int l = 1, int r = n) {
  if (l == r) {
    s[id] = {array<int, 2>{0, inf}, array<int, 2>{inf, 0}};
    return;
  }
  int md = (l + r) / 2;
  bld(id * 2, l, md);
  bld(id * 2 + 1, md + 1, r);
  s[id] = s[id * 2] + s[id * 2 + 1];
}

void upd(int i, int id = 1, int l = 1, int r = n) {
  if (l == r) {
    int u = pos[i];
    if (state[u] == 1) {
      s[id][0] = {inf, inf};
    } else {
      s[id][0] = {sum[u][0], inf};
    }
    if (state[u] == 2) {
      s[id][1] = {inf, inf};
    } else {
      s[id][1] = {inf, sum[u][1]};
    }
    return;
  } 
  int md = (l + r) / 2;
  if (i <= md) {
    upd(i, id * 2, l, md);
  } else {
    upd(i, id * 2 + 1, md + 1, r);
  }
  s[id] = s[id * 2] + s[id * 2 + 1];
}

void dfs(int u) {
  for (int &v : g[u]) {
    if (v == pr[u]) {
      swap(v, g[u].back());
      g[u].pop_back();
      break;
    }
  }
  sz[u] = 1;
  for (int v : g[u]) {
    pr[v] = u;
    dfs(v);
    sz[u] += sz[v];
  }
}

int order;

void hld(int u, int h) {
  head[u] = h;  
  pos[tin[u] = tail[h] = ++order] = u;
  if (g[u].size()) {
    int x = *max_element(g[u].begin(), g[u].end(), [&](int i, int j) {
      return sz[i] < sz[j];
    });
    hld(x, h);
    for (int v : g[u]) {
      if (v != x) {
        hld(v, v);
      }
    }
  }
}

Node qry(int u, int v, int id = 1, int l = 1, int r = n) {
  if (u <= l && r <= v) {
    return s[id];
  }
  int md = (l + r) / 2;
  if (v <= md) {
    return qry(u, v, id * 2, l, md);
  }
  if (md < u) {
    return qry(u, v, id * 2 + 1, md + 1, r);
  }
  return qry(u, v, id * 2, l, md) + qry(u, v, id * 2 + 1, md + 1, r);
} 

int chg(int u, int x) {
  state[u] = x;
  for (; u; u = pr[head[u]]) {
    upd(tin[u]);
    u = head[u];
    int p = pr[u];
    auto dat = qry(tin[u], tail[u]);
    array<int, 2> c{min(dat[0][0], dat[0][1]), min(dat[1][0], dat[1][1])};
    for (auto it : {0, 1}) {
      sum[p][it] -= up[u][it];
      up[u][it] = min(c[it], c[it ^ 1] + 1);
      sum[p][it] += up[u][it];
    }
  }
  int res = inf;
  auto dat = qry(tin[1], tail[1]);
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j) {
      res = min(res, dat[i][j]);
    }
  }
  return res;
}

void initialize(int N, std::vector<int> A, std::vector<int> B) {
  n = N;
  for (int i = 0; i < n - 1; ++i) {
    g[A[i]].push_back(B[i]);
    g[B[i]].push_back(A[i]);
  }
  bld();
  dfs(1);
  hld(1, 1);
}

int cat(int v) {
  return chg(v, 2);
}

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

int neighbor(int v) {
  return chg(v, 0);
}

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