Submission #59011

#	Time	Username	Problem	Language	Result	Execution time	Memory
59011		gusfring	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	455 ms	81536 KiB

catdog

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

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

const ll inf = 1e16;
const int MAXN = 1e6 + 5, MAXNN = 1e5 + 5;

struct node {
  ll val[2][2];
  node(){
    val[0][0] = val[1][1] = 0, val[0][1] = val[1][0] = inf;
  }
  node operator+(const node &p) const{
    node ret;
    for(int i=0; i<2; ++i)
      for(int j=0; j<2; ++j){
        ret.val[i][j] = inf;
        for(int k=0; k<2; ++k)
          for(int l=0; l<2; ++l)
            ret.val[i][j] = min(ret.val[i][j], val[i][k] + p.val[l][j] + (k ^ l));
      }
    return ret;
  }
};

struct segtree{
  vector<node> val;
  int sz;
  void init(int root, int lo, int hi){
    if(lo == hi) return;
    int mid = (lo + hi)>>1, left = root<<1, right = left | 1;
    init(left, lo, mid);
    init(right, mid + 1, hi);
    val[root] = val[left] + val[right];
  }
  void init(int n){
    int s = 1;
    sz = n;
    while(s < (sz << 1)) s <<= 1;
    val.resize(s);
    init(1, 1, sz);
  }
  void update(int root, int lo, int hi, int x, ll v0, ll v1){
    if(lo == hi){
      val[root].val[0][0] += v0;
      val[root].val[1][1] += v1;
      return;
    }
    int mid = (lo + hi)>>1, left = root<<1, right = left | 1;
    if(x <= mid) update(left, lo, mid, x, v0, v1);
    else update(right, mid + 1, hi, x, v0, v1);
    val[root] = val[left] + val[right];
  }
  void update(int pos, ll x0, ll x1){
    update(1, 1, sz, pos, x0, x1);
  }
  pii query() const{
    int x = min(val[1].val[0][0], val[1].val[0][1]);
    int y = min(val[1].val[1][0], val[1].val[1][1]);
    return pii(min(x, y + 1), min(x + 1, y));
  }
} seg[MAXNN];

int n;
vector<int> edge[MAXNN];
int sz[MAXNN], pathPar[MAXNN], pathPos[MAXNN], par[MAXNN], st[MAXNN];

void dfsSize(int x, int p){
  par[x] = p, sz[x] = 1;
  for(int i : edge[x]){
    if(i == p) continue;
    dfsSize(i, x);
    sz[x] += sz[i];
  }
}

void dfsDecomp(int x, int p){
  int hpath = 0;
  for(int i : edge[x]){
    if(i == p) continue;
    if(sz[x] <= (sz[i] << 1)){
        hpath = i;
        break;
    }
  }
  if(hpath == 0) seg[pathPar[x]].init(pathPos[x]);
  for(int i : edge[x]){
    if(i == p) continue;
    if(i != hpath){
      pathPar[i] = i;
      pathPos[i] = 1;
    }
    else{
      pathPar[i] = pathPar[x];
      pathPos[i] = pathPos[x] + 1;
    }
    dfsDecomp(i, x);
  }
}

void initialize(int N, vector<int> A, vector<int> B) {
  n = N;
  for(int i=0; i<n-1; ++i){
    edge[A[i]].push_back(B[i]);
    edge[B[i]].push_back(A[i]);
  }
  dfsSize(1, 0);
  pathPar[1] = 1, pathPos[1] = 1;
  dfsDecomp(1, 0);
}

void update(int x, int v0, int v1) {
  while(x){
    int path = pathPar[x];
    int pr0, pr1, nx0, nx1;
    tie(pr0, pr1) = seg[path].query();
    seg[path].update(pathPos[x], v0, v1);
    tie(nx0, nx1) = seg[path].query();
    v0 = nx0 - pr0;
    v1 = nx1 - pr1;
    x = par[pathPar[x]];
  }
}

int getAns(){
  pii it = seg[1].query();
  return min(it.first, it.second);
}

int cat(int v){
  st[v] = 1;
  update(v, MAXN, 0);
  return getAns();
}

int dog(int v){
  st[v] = 2;
  update(v, 0, MAXN);
  return getAns();
}

int neighbor(int v){
  if(st[v] == 1) update(v, -MAXN, 0);
  else update(v, 0, -MAXN);
  st[v] = 0;
  return getAns();
}

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