Submission #497592

#	Time	Username	Problem	Language	Result	Execution time	Memory
497592		600Mihnea	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	1014 ms	33820 KiB

catdog

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

using namespace std;

const int N = (int) 1e5 + 7;
const int INF = (int) 1e8;
int n, sub[N], child[N], color[N], par[N], y, dp1[N], dp2[N], cost1[N], cost2[N], theindex[N], curind, node[N], l1[N], l2[N];
vector<int> members[N];
bool isTheChild[N];
vector<int> g[N];

struct D {
  bool nmc;
  int cost[2][2];
};

D operator + (D a, D b) {
  if (a.nmc) {
    return b;
  }
  if (b.nmc) {
    return a;
  }
  D c;
  c.nmc = 0;
  for (int i = 0; i < 2; i++) {
    for (int j = 0; j < 2; j++) {
      c.cost[i][j] = INF;
    }
  }
  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++) {
          c.cost[i][l] = min(c.cost[i][l], a.cost[i][j] + b.cost[k][l] + (j != k));
        }
      }
    }
  }
  return c;
}

D t[4 * N];
D wnmc;

void upd(int v, int tl, int tr, int i) {
  if (tr < i || i < tl) {
    return;
  }
  if (tl == tr) {
    vector<int> K = {cost1[node[i]] + dp1[node[i]], cost2[node[i]] + dp2[node[i]]};
    t[v].cost[0][1] = t[v].cost[1][0] = INF;
    t[v].cost[0][0] = K[0];
    t[v].cost[1][1] = K[1];
    return;
  }
  int tm = (tl + tr) / 2;
  upd(2 * v, tl, tm, i);
  upd(2 * v + 1, tm + 1, tr, i);
  t[v] = t[2 * v] + t[2 * v + 1];
}

D get(int v, int tl, int tr, int l, int r) {
  if (tr < l || r < tl) {
    return wnmc;
  }
  if (l <= tl && tr <= r) {
    return t[v];
  }
  int tm = (tl + tr) / 2;
  D x = get(2 * v, tl, tm, l, r);
  D y = get(2 * v + 1, tm + 1, tr, l, r);
  D z = x + y;
  return x + y;
}

void buildtr(int v = 1, int tl = 0, int tr = n) {
  if (tl == tr) {
    t[v].cost[0][1] = t[v].cost[1][0] = INF;
    t[v].cost[0][0] = t[v].cost[1][1] = 0;
  } else {
    int tm = (tl + tr) / 2;
    buildtr(2 * v, tl, tm);
    buildtr(2 * v + 1, tm + 1, tr);
    t[v] = t[2 * v] + t[2 * v + 1];
  }
}


void build(int a, int p = 0) {
  vector<int> kids;
  sub[a] = 1;
  par[a] = p;
  for (auto &b : g[a]) {
    if (b != p) {
      kids.push_back(b);
      build(b, a);
      sub[a] += sub[b];
      if (sub[b] > sub[child[a]]) {
        child[a] = b;
      }
    }
  }
  isTheChild[child[a]] = 1;
  g[a] = kids;
}

void compute(int a) {
  if (isTheChild[a]) {
    color[a] = color[par[a]];
  } else {
    color[a] = ++y;
  }
  theindex[a] = ++curind;
  node[theindex[a]] = a;
  members[color[a]].push_back(a);
  if (child[a]) {
    compute(child[a]);
    for (auto &b : g[a]) {
      if (b != child[a]) {
        compute(b);
      }
    }
  }
}

void updVertex(int v) {
  int p = par[members[color[v]][0]];

  dp1[p] -= l1[color[v]];
  dp2[p] -= l2[color[v]];

  upd(1, 0, n, theindex[v]);

  D sol = get(1, 0, n, theindex[members[color[v]][0]], theindex[members[color[v]].back()]);

  l1[color[v]] = min(sol.cost[0][0], sol.cost[0][1]);
  l2[color[v]] = min(sol.cost[1][0], sol.cost[1][1]);

  l1[color[v]] = min(l1[color[v]], l2[color[v]] + 1);
  l2[color[v]] = min(l2[color[v]], l1[color[v]] + 1);


  dp1[p] += l1[color[v]];
  dp2[p] += l2[color[v]];
}


void update(int node) {
  while (node) {
    updVertex(node);
    node = par[members[color[node]][0]];
  }
}


void initialize(int nn, std::vector<int> edgesA, std::vector<int> edgesB) {
  wnmc.nmc = 1;
  n = nn;
  buildtr();
  for (int i = 0; i < n - 1; i++) {
    int a = edgesA[i];
    int b = edgesB[i];
    g[a].push_back(b);
    g[b].push_back(a);
  }
  build(1);
  compute(1);
}

void changeCost(int v, int c1, int c2) {
  dp1[v] -= cost1[v];
  dp2[v] -= cost2[v];

  cost1[v] = c1;
  cost2[v] = c2;

  dp1[v] += cost1[v];
  dp2[v] += cost2[v];


  updVertex(v);

  update(v);

}

int eval() {
  return min(dp1[0], dp2[0]);
}

int cat(int v) {
  changeCost(v, 0, INF);
  return eval();
}

int dog(int v) {
  changeCost(v, INF, 0);
  return eval();
}


int neighbor(int v) {
  changeCost(v, 0, 0);
  return eval();

}

Compilation message (stderr)

catdog.cpp: In function 'D get(int, int, int, int, int)':
catdog.cpp:74:5: warning: variable 'z' set but not used [-Wunused-but-set-variable]
   74 |   D z = x + y;
      |     ^

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