답안 #492944

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
492944 2021-12-09T20:13:52 Z ivan_tudor Cats or Dogs (JOI18_catdog) C++14
컴파일 오류
0 ms 0 KB
#include "catdog.h"
using namespace std;
const int N = 100005;
const int INF = 1e9;
int n;
int scores[2][N];
int curl[2][N];
struct SegmentTree{
  int ans[2][2];
  SegmentTree(){
    for(int i =0; i< 2; i++){
      for(int j = 0; j < 2; j++)
        ans[i][j] = INF;
    }
  }
  SegmentTree(int val){
    for(int i =0; i< 2; i++){
      for(int j = 0; j < 2; j++)
        ans[i][j] = val;
    }
  }
};
SegmentTree NULL(0);
SegmentTree join(SegmentTree a, SegmentTree b){
  SegmentTree rsp;
  for(int i = 0; i <= 1; i++){
    for(int j = 0; j <= 1; j++){
      for(int midl = 0; midl <=1 ;midl++){
        for(int midr = 0; midr <=1; midr++){
          rsp.ans[i][j] = min(rsp.ans[i][j], rsp.ans[i][midl] + rsp.ans[midr][j] + (midl!=midr));
        }
      }
    }
  }
  return rsp;
}
SegmentTree build(int nod, int animal){
  SegmentTree rsp;
  for(int i =0; i <= 1; i++){
    if(animal == i || animal == 2)
      rsp.ans[i][i] = 0;
    rsp.ans[i][i] += scores[i][nod];
  }
  return rsp;
}
SegmentTree aint[4*N];
int getminscore(SegmentTree chain, int pet){
  int ans = INF;
  for(int i = 0; i <= 1; i++){
    ans = min(ans, chain.ans[pet][i]);
    ans = min(ans, chain.ans[pet^1][i] + 1);
  }
  return ans;
}
void update(int nod, int l, int r, int upoz, int utype){
  if(l > upoz || r < upoz)
    return;
  if(l == r){
    aint[nod] = build(nod, utype);
    return;
  }
  int mid = (l + r)/2;
  update(2*nod, l, mid, upoz, utype);
  update(2*nod + 1, mid +1, r, upoz, utype);
  aint[nod] = join(aint[2*nod], aint[2*nod + 1]);
}
SegmentTree query(int nod, int l, int r, int ql, int qr){
  if(qr < l || ql > r)
    return NULL;
  if(l <= ql && qr <= r)
    return aint[nod];
  int mid = (l + r)/2;
  SegmentTree rsp;
  rsp = join(query(2*nod, l, mid, ql, qr), query(2*nod + 1, mid + 1, r, ql, qr));
  return rsp;
}

vector<int> gr[N];
int par[N];
int sz[N];
int id[N];
int head[N];
int tp[N];
void dfs_init(int nod, int dad){
  par[nod] = dad;
  sz[nod] = 1;
  for(auto x:gr[nod]){
    if(x == dad)
      continue;
    dfs_init(x, nod);
    sz[nod] += sz[x];
  }
}
void dfs_heavy(int nod, int dad,int &idd, int chead){
  head[nod] = chead;
  id[nod] = idd++;
  int mson = -1;
  for(auto x:gr[nod]){
    if(x == dad)
      continue;
    if(mson == -1 || sz[x] > sz[mson])
      mson = x;
  }
  if(mson == -1)
    return;
  dfs_heavy(mson, nod, idd, chead);
  for(auto x:gr[nod]){
    if(x == dad || x == mson)
      continue;
    dfs_heavy(x, nod, idd, nod);
  }
}
SegmentTree update_heavy(int nod, int type){
  tp[nod] = type;
  int hd = head[nod];
  update(1, 1, n, id[nod], type);
  SegmentTree chain = query(1, 1, n, id[hd], id[nod]);
  if(hd == 1)
    return chain;
  for(int i = 0; i<=1; i++){
    scores[i][id[par[hd]]] -= curl[i][id[hd]];
    curl[i][id[hd]] = getminscore(chain, i);
    scores[i][id[par[hd]]] += curl[i][id[hd]];
  }
  return update_heavy(par[hd], tp[par[hd]]);
}

void build_aint(int nod, int l, int r){
  if(l == r){
    aint[nod] = build(nod, tp[nod]);
    return;
  }
  int mid = (l + r)/2;
  build_aint(2*nod, l, mid);
  build_aint(2*nod + 1, mid + 1, r);
  aint[nod] = join(aint[2*nod], aint[2*nod + 1]);
}

void initialize(int N, std::vector<int> A, std::vector<int> B){
  n = N;
  for(int i = 0; i < N - 1; i++){
    gr[A[i]].push_back(B[i]);
    gr[B[i]].push_back(A[i]);
  }
  for(int i = 1; i<=n; i++)
    tp[i] = 2;
  build_aint(1,  1,  n);
  dfs_init(1, 0);
  int cnt = 1;
  dfs_heavy(1, 0, cnt, 1);
};
int cat(int v){
  SegmentTree rsp = update_heavy(v, 0);
  return min(getminscore(rsp, 0), getminscore(rsp, 1));
}
int dog(int v){
  SegmentTree rsp = update_heavy(v, 1);
  return min(getminscore(rsp, 0), getminscore(rsp, 1));
}
int neighbor(int v){
  SegmentTree rsp = update_heavy(v, 2);
  return min(getminscore(rsp, 0), getminscore(rsp, 1));
}

Compilation message

In file included from /usr/include/c++/10/bits/cxxabi_init_exception.h:38,
                 from /usr/include/c++/10/bits/exception_ptr.h:38,
                 from /usr/include/c++/10/exception:147,
                 from /usr/include/c++/10/new:41,
                 from /usr/include/c++/10/ext/new_allocator.h:33,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
                 from /usr/include/c++/10/bits/allocator.h:46,
                 from /usr/include/c++/10/vector:64,
                 from catdog.h:3,
                 from catdog.cpp:1:
catdog.cpp:23:13: error: expected unqualified-id before '__null'
   23 | SegmentTree NULL(0);
      |             ^~~~
catdog.cpp: In function 'SegmentTree query(int, int, int, int, int)':
catdog.cpp:69:12: warning: passing NULL to non-pointer argument 1 of 'SegmentTree::SegmentTree(int)' [-Wconversion-null]
   69 |     return NULL;
      |            ^~~~
catdog.cpp:16:19: note:   declared here
   16 |   SegmentTree(int val){
      |               ~~~~^~~