제출 #415774

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
415774		MarcoMeijer	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	2189 ms	63044 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;

#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define RE1(a,b) REP(a,1,b+1)
#define FOR(a,b) for(auto& a : b)
#define pb push_back
#define all(a) a.begin(),a.end()
#define fi first
#define se second

const int INF	= 1e6;
const int MX	= 2e5;
const int N	  = 1<<20;
const int MOD	= 1e9+7;

int n;
int a[MX];

// tree stuff
vi adj[MX], chl[MX];
int sz[MX], par[MX], dep[MX];
void dfs(int u, int p) {
  sz[u] = 1;
  par[u] = p;
  dep[u] = dep[p]+1;
  FOR(v,adj[u]) {
    if(v == p) continue;
    dfs(v,u);
    sz[u] += sz[v];
    chl[u].pb(v);
  }
}

// hld
int hd[MX], tl[MX], segi[MX], curseg=0;
void HLD(int u, int head) {
  hd[u] = head;
  segi[u] = curseg++;
  tl[head] = u;
  tl[u] = u;
  if(chl[u].empty()) return;
  int bst = chl[u][0];
  FOR(v,chl[u]) if(sz[v]>sz[bst]) bst = v;
  HLD(bst,head);
  FOR(v,chl[u]) if(v != bst) HLD(v,v);
  tl[u] = tl[head];
}

// seg
struct T {
  T() {
    RE(j,2) a[j][ j] = 0;
    RE(j,2) a[j][!j] = INF;
  }
  int a[2][2];
};
T seg[N*2];
T combine(T a, T b) {
  T res;
  RE(i,2) RE(j,2) res.a[i][j] = INF;
  RE(i,2) RE(j,2) RE(k,2) RE(l,2)
    res.a[i][l] = min(res.a[i][l], a.a[i][j] + b.a[k][l] + (j==k?0:1));
  return res;
}
void combine(int p) {
  seg[p] = combine(seg[p*2], seg[p*2+1]);
}
void buildSeg(int p=1, int l=0, int r=N-1) {
  if(l == r) {
    RE(j,2) seg[p].a[j][ j] = 0;
    RE(j,2) seg[p].a[j][!j] = INF;
    return;
  }
  int m=(l+r)/2;
  buildSeg(p*2,l,m);
  buildSeg(p*2+1,m+1,r);
  combine(p);
}
void addSeg(int i, int x, int v, int p=1, int l=0, int r=N-1) {
  if(i < l || i > r) return;
  if(l == r) {
    seg[p].a[x][x] += v;
    return;
  }
  int m=(l+r)/2;
  addSeg(i,x,v,p*2,l,m);
  addSeg(i,x,v,p*2+1,m+1,r);
  combine(p);
}
T getSeg(int i, int j, int p=1, int l=0, int r=N-1) {
  if(j < l || i > r) return {};
  if(i <= l && j >= r) return seg[p];
  int m=(l+r)/2;
  T a=getSeg(i,j,p*2,l,m);
  T b=getSeg(i,j,p*2+1,m+1,r);
  return combine(a,b);
}

// updates
int ans=0;
int getRes(T a, int x) {
  return min(a.a[x][0], a.a[x][1]);
}
void update(int u, int v1, int v2) {
  while(true) {
    T oldValue = getSeg(segi[hd[u]], segi[tl[u]]);
    addSeg(segi[u], 0, v1);
    addSeg(segi[u], 1, v2);
    T newValue = getSeg(segi[hd[u]], segi[tl[u]]);
    if(hd[u] == 1) {
      ans = INF;
      RE(i,2) RE(j,2) ans = min(ans, newValue.a[i][j]);
      break;
    } else {
      v1 = getRes(newValue,0) - getRes(oldValue,0);
      v2 = getRes(newValue,1) - getRes(oldValue,1);
      u = par[hd[u]];
    }
  }
}

// init
void initialize(int N, std::vector<int> A, std::vector<int> B) {
  n = N;
  RE(i,n-1) {
    adj[A[i]].pb(B[i]);
    adj[B[i]].pb(A[i]);
  }
  dfs(1,1);
  HLD(1,1);
  buildSeg();
}

// interaction
int cat(int v) {
  a[v] = 1;
  update(v,INF,0);
  return ans;
}
int dog(int v) {
  a[v] = 2;
  update(v,0,INF);
  return ans;
}
int neighbor(int v) {
  if(a[v] == 1) update(v,-INF,0);
  if(a[v] == 2) update(v,0,-INF);
  a[v] = 0;
  return ans;
}

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