Submission #384121

#	Time	Username	Problem	Language	Result	Execution time	Memory
384121		qwerty234	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	310 ms	31468 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;

const int MAXN = 1e5 + 10, inf = 1e9;

struct node {
  int rr, rb, br, bb, r, b;
  node() {
    rb = br = inf;
    rr = bb = r = b = 0;
  }
};

int n;
vector <int> s, parent, heavy, head, col, cnt, order;
vector < vector <int>> g;
vector < vector <node>> t;

node merge(node &b, node &c) {
  node a = node();
  a.rr = a.bb = a.rb = a.br = inf;
  a.rr = min(a.rr, min(b.rr + c.rr, b.rr + c.br + 1)); a.rr = min(a.rr, min(b.rb + c.rr + 1, b.rb + c.br));
  a.rb = min(a.rb, min(b.rr + c.rb, b.rr + c.bb + 1)); a.rb = min(a.rb, min(b.rb + c.rb + 1, b.rb + c.bb));
  a.bb = min(a.bb, min(b.br + c.rb, b.br + c.bb + 1)); a.bb = min(a.bb, min(b.bb + c.rb + 1, b.bb + c.bb));
  a.br = min(a.br, min(b.br + c.rr, b.br + c.br + 1)); a.br = min(a.br, min(b.bb + c.rr + 1, b.bb + c.br));
  a.r = b.r;
  a.b = b.b;
  return a;
}

void build(int id, int v, int tl, int tr) {
  if (tl == tr) {
    t[id][v] = node();
    return;
  }
  int tm = (tl + tr)>>1;
  build(id, (v << 1), tl, tm);
  build(id, ((v << 1)|1), tm + 1, tr);
  t[id][v] = merge(t[id][(v << 1)], t[id][((v << 1)|1)]);
}

void upd(int id, int v, int tl, int tr, int pos, int c, int dr, int db) {
  if (tl == tr) {
    if (c == -1) {
      t[id][v].r += dr;
      t[id][v].b += db;
      if (t[id][v].rr != inf) t[id][v].rr += dr;
      if (t[id][v].bb != inf) t[id][v].bb += db;
      // cout << id << " " << v << " " << c << " " << dr << " " << db << " " << t[id][v].rr << " " << t[id][v].bb << endl;
    } else if (c == 0) {
      t[id][v].rr = t[id][v].r;
      t[id][v].bb = t[id][v].b;
    } else if (c == 1) {
      t[id][v].rr = t[id][v].r;
      t[id][v].bb = inf;
      // cout << id << " " << v << " " << c << " " << dr << " " << db << " " << t[id][v].rr << " " << t[id][v].bb << endl;
    } else {
      t[id][v].rr = inf;
      t[id][v].bb = t[id][v].b;
      // cout << id << " " << v << " " << c << " " << dr << " " << db << " " << t[id][v].rr << " " << t[id][v].bb << endl;
    }
    return;
  }
  int tm = (tl + tr)>>1;
  if (pos <= tm)
    upd(id, (v << 1), tl, tm, pos, c, dr, db);
  else
    upd(id, ((v << 1)|1), tm + 1, tr, pos, c, dr, db);
  t[id][v] = merge(t[id][(v << 1)], t[id][((v << 1)|1)]);
  node a = t[id][v];
  // cout << id << " " << tl << " " << tr << " " << a.rr << " " << a.bb << " " << a.rb << " " << a.br << endl;
}

pair<node, bool> get(int id, int v, int tl, int tr, int l, int r) {
  if (r < tl || tr < l) return {node(), false};
  if (l <= tl && tr <= r) {
    node a = t[id][v];
    // cout << id << " " << tl << " " << tr << " " << l << " " << r << " " << a.rr << " " << a.bb << " " << a.rb << " " << a.br << endl;
    return {t[id][v], true};
  }
  int tm = (tl + tr)>>1;
  pair<node, bool> b = get(id, (v << 1), tl, tm, l, r), c = get(id, ((v << 1)|1), tm + 1, tr, l, r);
  if (!b.se) return c;
  if (!c.se) return b;
  node a = merge(b.fi, c.fi);
  // cout << id << " " << tl << " " << tr << " " << l << " " << r << " " << a.rr << " " << a.bb << " " << a.rb << " " << a.br << endl;
  return {merge(b.fi, c.fi), true};
}

void dfs(int u, int p) {
  s[u] = 1;
  parent[u] = p;
  heavy[u] = -1;
  pair<int, int> mx = {-1, -1};
  for (int to : g[u]) {
    if (to == p)
      continue;
    dfs(to, u);
    s[u] += s[to];
    mx = max(mx, {s[to], to});
  }
  if (mx.fi * 2 >= s[u]) heavy[u] = mx.se;
}

int x;
void decompose(int u, int last, int orderr) {
  head[u] = last;
  col[u] = x;
  cnt[col[u]]++;
  order[u] = orderr;
  if (heavy[u] != -1) decompose(heavy[u], last, orderr + 1);
  for (int to : g[u]) {
    if (to == parent[u] || to == heavy[u])
      continue;
    x++;
    decompose(to, to, 0);
  }
}

void initialize(int N, vector <int> A, vector <int> B) {
  n = N;
  s.assign(n, 0);
  parent.assign(n, 0);
  heavy.assign(n, -1);
  head.assign(n, 0);
  col.assign(n, 0);
  cnt.assign(n, 0);
  order.assign(n, 0);
  g.assign(n, {});
  // cout << "ok" << endl;
  for (int i = 0; i < n - 1; i++) {
    A[i]--; B[i]--;
    g[A[i]].pb(B[i]);
    g[B[i]].pb(A[i]);
  }
  dfs(0, -1);
  x = 0;
  decompose(0, 0, 0);
  // cout << "ok" << endl;
  x++;
  t.assign(x, {});
  for (int i = 0; i < x; i++) {
    t[i].resize(4 * cnt[i]);
    build(i, 1, 0, cnt[i] - 1);
  }
  // cout << "ok" << endl;
  // for (int i = 0; i < n; i++)
  //   cout << i + 1 << " " << parent[i] + 1 << " " << head[i] + 1 << " " << s[i] << " " << heavy[i] + 1 << " " << col[i] << " " << cnt[col[i]] << endl;
  // exit(0);
}

int query(int v, int val) {
  v--;
  // cout << "query " << v + 1 << " " << val << " " << head[v] << endl;
  int cur = head[v], dr, db;
  node n1, n2;
  n1 = get(col[cur], 1, 0, cnt[col[cur]] - 1, 0, cnt[col[cur]] - 1).fi;
  upd(col[v], 1, 0, cnt[col[v]] - 1, order[v], val, 0, 0);
  while (cur != 0) {
    n2 = get(col[cur], 1, 0, cnt[col[cur]] - 1, 0, cnt[col[cur]] - 1).fi;
    dr = min(min(n2.rb, n2.rr), min(n2.bb, n2.br) + 1) - min(min(n1.rb, n1.rr), min(n1.bb, n1.br) + 1);
    db = min(min(n2.rb, n2.rr) + 1, min(n2.bb, n2.br)) - min(min(n1.rb, n1.rr) + 1, min(n1.bb, n1.br));
    n1 = get(col[parent[cur]], 1, 0, cnt[col[parent[cur]]] - 1, 0, cnt[col[parent[cur]]] - 1).fi;
    // cout << cur + 1 << " " << parent[cur] + 1 << " " << dr << " " << db << endl;
    upd(col[parent[cur]], 1, 0, cnt[col[parent[cur]]] - 1, order[parent[cur]], -1, dr, db);
    cur = head[parent[cur]];
  }
  n1 = get(col[cur], 1, 0, cnt[col[cur]] - 1, 0, cnt[col[cur]] - 1).fi;
  return min(min(n1.rr, n1.bb), min(n1.rb, n1.br));
}

int cat(int v) {
  return query(v, 1);
}

int dog(int v) {
  return query(v, 2);
}

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

Compilation message (stderr)

catdog.cpp: In function 'void upd(int, int, int, int, int, int, int, int)':
catdog.cpp:74:8: warning: variable 'a' set but not used [-Wunused-but-set-variable]
   74 |   node a = t[id][v];
      |        ^
catdog.cpp: In function 'std::pair<node, bool> get(int, int, int, int, int, int)':
catdog.cpp:81:10: warning: variable 'a' set but not used [-Wunused-but-set-variable]
   81 |     node a = t[id][v];
      |          ^
catdog.cpp:89:8: warning: variable 'a' set but not used [-Wunused-but-set-variable]
   89 |   node a = merge(b.fi, c.fi);
      |        ^

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