Submission #937166

#	Time	Username	Problem	Language	Result	Execution time	Memory
937166		nguyentunglam	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	522 ms	27000 KiB

catdog

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;

const int N = 1e5 + 10;

int n, a[N], c[N], d[N];

int heavy[N], sz[N], rev_st[N], st[N], ed[N], p[N], root[N], timer;

vector<int> adj[N];

struct dp {
  int f[2][2];
};

dp T[N << 2];

dp zero, _zero;

dp gather (dp left, dp right) {
  dp ret;
  if (left.f[0][0] < 0) return right;
  if (right.f[0][0] < 0) return left;
  for(int x = 0; x < 2; x++) for(int y = 0; y < 2; y++) {
    ret.f[x][y] = 1e9;
    for(int z = 0; z < 2; z++) {
      ret.f[x][y] = min({ret.f[x][y], left.f[x][z] + right.f[z][y], left.f[x][z] + right.f[z ^ 1][y] + 1});
    }
    assert(ret.f[x][y] <= 1e9);
  }
  return ret;
}

void up (int s, int l, int r, int pos) {
  if (l == r) {
    int u = rev_st[pos];
    T[s] = zero;
    if (a[u] != 2) T[s].f[0][0] = c[u];
    if (a[u] != 1) T[s].f[1][1] = d[u];
//    cout << T[s].f[0][0] << " " << T[s].f[0][1] << " " << T[s].f[1][0] << " " << T[s].f[1][1] << endl;
    return;
  }
  int mid = l + r >> 1;
  if (pos <= mid) up(s << 1, l, mid, pos);
  else up(s << 1 | 1, mid + 1, r, pos);
  T[s] = gather(T[s << 1], T[s << 1 | 1]);
//  if (pos == 2) {
//    cout << l << " " << r << endl;
//    cout << T[s].f[0][0] << " " << T[s].f[0][1] << " " << T[s].f[1][0] << " " << T[s].f[1][1] << endl;
//  }
}

dp get (int s, int l, int r, int from, int to) {
  if (l > to || r < from) return _zero;
  if (from <= l && r <= to) return T[s];
  int mid = l + r >> 1;
  return gather(get(s << 1, l, mid, from, to), get(s << 1 | 1, mid + 1, r, from, to));
}

void dfs(int u) {
  sz[u] = 1;
  for(int &v : adj[u]) if (!sz[v]) {
    p[v] = u;
    dfs(v);
    sz[u] += sz[v];
    if (sz[v] > sz[heavy[u]]) heavy[u] = v;
  }
}

void hld (int u) {
  st[u] = ++timer;
  rev_st[timer] = u;
  if (!root[u]) root[u] = u;
  ed[root[u]] = timer;

  if (heavy[u]) {
    root[heavy[u]] = root[u];
    hld(heavy[u]);
  }

  for(int &v : adj[u]) if (v != heavy[u] && v != p[u]) hld(v);
}

void print(dp x) {
  cout << x.f[0][0] << " " << x.f[0][1] << " " << x.f[1][0] << " " << x.f[1][1] << endl;
}

void initialize (int N, vector<int> A, vector<int> B) {
  n = N;
  zero.f[0][0] = zero.f[0][1] = zero.f[1][0] = zero.f[1][1] = 1e9;
  _zero.f[0][0] = _zero.f[0][1] = _zero.f[1][0] = _zero.f[1][1] = -1;
  for(int i = 0; i < n - 1; i++) {
    adj[A[i]].push_back(B[i]);
    adj[B[i]].push_back(A[i]);
  }
  dfs(1);
  hld(1);
  for(int i = 1; i <= n; i++) up(1, 1, n, i);
}

int update(int u) {
  while (1) {
    dp old = zero;
    if (root[u] != 1) old = get(1, 1, n, st[root[u]], ed[root[u]]);
    up(1, 1, n, st[u]);
    dp nxt = get(1, 1, n, st[root[u]], ed[root[u]]);
//    print(nxt);
    u = p[root[u]];
    if (u == 0) return min({nxt.f[0][0], nxt.f[0][1], nxt.f[1][0], nxt.f[1][1]});
    else {
      int _c, _d;
      _c = min(old.f[0][0], old.f[0][1]);
      _d = min(old.f[1][0], old.f[1][1]);
      c[u] -= min(_c, _d + 1);
      d[u] -= min(_d, _c + 1);

      _c = min(nxt.f[0][0], nxt.f[0][1]);
      _d = min(nxt.f[1][0], nxt.f[1][1]);
      c[u] += min(_c, _d + 1);
      d[u] += min(_d, _c + 1);
    }
  }
}

int cat(int v) {
  a[v] = 1;
  return update(v);
}

int dog(int v) {
  a[v] = 2;
  return update(v);
}

int neighbor(int v) {
  a[v] = 0;
  return update(v);
}

#ifdef ngu
int main() {

  freopen ("task.inp", "r", stdin);
  freopen ("task.out", "w", stdout);

  int n; cin >> n;

  vector<int> a(n - 1), b(n - 1);

  for(int i = 0; i < n - 1; i++) cin >> a[i] >> b[i];

  initialize(n, a, b);

  int q; cin >> q;

  while (q--) {
    int t, v; cin >> t >> v;
    if (t == 1) cout << cat(v);
    if (t == 2) cout << dog(v);
    if (t == 3) cout << neighbor(v);
    cout << endl;
  }
}
#endif // ngu

Compilation message (stderr)

catdog.cpp: In function 'void up(int, int, int, int)':
catdog.cpp:47:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   int mid = l + r >> 1;
      |             ~~^~~
catdog.cpp: In function 'dp get(int, int, int, int, int)':
catdog.cpp:60:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |   int mid = l + r >> 1;
      |             ~~^~~

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