Submission #800265

#	Time	Username	Problem	Language	Result	Execution time	Memory
800265		MilosMilutinovic	Cats or Dogs (JOI18_catdog)	C++14	0 / 100	1 ms	2644 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX = (int) 1e5;

int n, sz[MAX], pr[MAX], hd[MAX];
int from[MAX], to[MAX], col[MAX];
int ver[MAX], id[MAX], rt[MAX];
int dp_a[MAX], dp_b[MAX];
vector<int> g[MAX];

struct node {
  int a[2][2];
  node() {}
  node(int v) {
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
        a[i][j] = v;
      }
    }
  }
} st[8 * MAX];

const int inf = (int) 1e9;

node f(node l, node r) {
  node res(inf);
  for (int xl = 0; xl < 2; xl++) {
    for (int yl = 0; yl < 2; yl++) {
      for (int xr = 0; xr < 2; xr++) {
        for (int yr = 0; yr < 2; yr++) {
          res.a[xl][yr] = min(res.a[xl][yr], l.a[xl][yl] + r.a[xr][yr] + (yl != xr ? 1 : 0));
        }
      }
    }
  }
  return res;
};

void pull(int v) {
  st[v] = f(st[v * 2], st[v * 2 + 1]);
}

void Build(int v, int l, int r) {
  if (l == r) {
    st[v].a[0][0] = dp_a[ver[l]];
    st[v].a[0][1] = inf;
    st[v].a[1][0] = inf;
    st[v].a[1][1] = dp_b[ver[l]];
    return;
  }
  int mid = l + r >> 1;
  Build(v * 2, l, mid);
  Build(v * 2 + 1, mid + 1, r);
  pull(v);
}

void Modify(int v, int l, int r, int i) {
  if (l == r) {
    st[v].a[0][0] = (col[ver[l]] != 1 ? dp_a[ver[l]] : inf);
    st[v].a[0][1] = inf;
    st[v].a[1][0] = inf;
    st[v].a[1][1] = (col[ver[l]] != 0 ? dp_b[ver[l]] : inf);
    return;
  }
  int mid = l + r >> 1;
  if (i <= mid) {
    Modify(v * 2, l, mid, i);
  } else {
    Modify(v * 2 + 1, mid + 1, r, i);
  }
  pull(v);
}

node Query(int v, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) {
    return st[v];
  }
  int mid = l + r >> 1;
  if (qr <= mid) {
    return Query(v * 2, l, mid, ql, qr);
  } else if (ql > mid) {
    return Query(v * 2 + 1, mid + 1, r, ql, qr);
  } else {
    return f(Query(v * 2, l, mid, ql, qr), Query(v * 2 + 1, mid + 1, r, ql, qr));
  }
}

void Update(int v) {
  while (true) {
    if (rt[v] != 0) {
      int x = pr[rt[v]];
      int y = rt[v];
      node nd = Query(1, 0, n - 1, from[y], to[y]);
      {
        dp_a[x] -= min({nd.a[0][0], nd.a[0][1], nd.a[1][0] + 1, nd.a[1][1] + 1});
        dp_b[x] -= min({nd.a[1][0], nd.a[1][1], nd.a[0][0] + 1, nd.a[0][1] + 1});
      }
    }
    Modify(1, 0, n - 1, id[v]);
    if (rt[v] != 0) {
      int x = pr[rt[v]];
      int y = rt[v];
      node nd = Query(1, 0, n - 1, from[y], to[y]);
      {
        dp_a[x] += min({nd.a[0][0], nd.a[0][1], nd.a[1][0] + 1, nd.a[1][1] + 1});
        dp_b[x] += min({nd.a[1][0], nd.a[1][1], nd.a[0][0] + 1, nd.a[0][1] + 1});
      }
      v = x;
    } else {
      return;
    }
  }
}

void initialize(int n, vector<int> x, vector<int> y) {
  ::n = n;
  for (int i = 0; i < n - 1; i++) {
    --x[i]; --y[i];
    g[x[i]].push_back(y[i]);
    g[y[i]].push_back(x[i]);
  }
  function<void(int, int)> dfs_hld = [&](int v, int p) {
    sz[v] = 1;
    hd[v] = -1;
    pr[v] = p;
    for (int u : g[v]) {
      if (u == p) {
        continue;
      }
      dfs_hld(u, v);
      sz[v] += sz[u];
      if (hd[v] == -1 || sz[u] > sz[hd[v]]) {
        hd[v] = u;
      }
    }
  };
  dfs_hld(0, -1);
  int cnt = 0;
  function<void(int, int)> dfs = [&](int v, int p) {
    if (hd[v] != -1) {
      rt[hd[v]] = rt[v];
      id[hd[v]] = cnt++;
      dfs(hd[v], v);
    }
    for (int u : g[v]) {
      if (u == p || u == hd[v]) {
        continue;
      }
      id[u] = cnt++;
      rt[u] = u;
      dfs(u, v);
    }
  };
  id[0] = cnt++;
  dfs(0, -1);
  for (int i = 0; i < n; i++) {
    ver[id[i]] = i;
  }
  Build(1, 0, n - 1);
  for (int i = 0; i < n; i++) {
    from[i] = n;
    to[i] = 0;
  }
  for (int i = 0; i < n; i++) {
    from[rt[i]] = min(from[rt[i]], id[i]);
    to[rt[i]] = max(to[rt[i]], id[i]);
  }
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    return id[i] > id[j];
  });
  for (int i : order) {
    for (int j : g[i]) {
      if (j == pr[i] || hd[i] == j) {
        continue;
      }
      node nd = Query(1, 0, n - 1, from[j], to[j]);
      dp_a[i] += min({nd.a[0][0], nd.a[0][1], nd.a[1][0] + 1, nd.a[1][1] + 1});
      dp_b[i] += min({nd.a[1][0], nd.a[1][1], nd.a[0][0] + 1, nd.a[0][1] + 1});
    }
    Modify(1, 0, n - 1, id[i]);
  }
}

int solve() {
  node nd = Query(1, 0, n - 1, from[0], to[0]);
  int res = inf;
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      res = min(res, nd.a[i][j]);
    }
  }
  return res;
}

int cat(int v) {
  --v;
  col[v] = 0;
  Update(v);
  return solve();
}

int dog(int v) {
  --v;
  col[v] = 1;
  Update(v);
  return solve();
}

int neighbor(int v) {
  --v;
  col[v] = -1;
  Update(v);
  return solve();
}

Compilation message (stderr)

catdog.cpp: In function 'void Build(int, int, int)':
catdog.cpp:54:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |   int mid = l + r >> 1;
      |             ~~^~~
catdog.cpp: In function 'void Modify(int, int, int, int)':
catdog.cpp:68:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |   int mid = l + r >> 1;
      |             ~~^~~
catdog.cpp: In function 'node Query(int, int, int, int, int)':
catdog.cpp:81:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |   int mid = l + r >> 1;
      |             ~~^~~

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