답안 #497587

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
497587 2021-12-23T10:19:21 Z 600Mihnea Cats or Dogs (JOI18_catdog) C++17
컴파일 오류
0 ms 0 KB
#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], index[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];
  }
}

int getdp1(int l, int r) {
  D sol = get(1, 0, n, l, r);
  return min(sol.cost[0][0], sol.cost[0][1]);
}

int getdp2(int l, int r) {
  D sol = get(1, 0, n, l, r);
  return min(sol.cost[1][0], sol.cost[1][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;
  }
  index[a] = ++curind;
  node[index[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, index[v]);

  l1[color[v]] = getdp1(index[members[color[v]][0]], index[members[color[v]].back()]);
  l2[color[v]] = getdp2(index[members[color[v]][0]], index[members[color[v]].back()]);

  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) {

    for (int j = 1; j < (int) members[color[node]].size(); j++) {
      assert(index[members[color[node]][j - 1]] == index[members[color[node]][j]] - 1);
    }

    int p = par[members[color[node]][0]];

    int i1 = getdp1(index[members[color[node]][0]], index[members[color[node]].back()]), i2 = getdp2(index[members[color[node]][0]], index[members[color[node]].back()]);


    updVertex(node);


    node = p;
  }
}


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

catdog.cpp:8:90: error: 'int index [100007]' redeclared as different kind of entity
    8 | int n, sub[N], child[N], color[N], par[N], y, dp1[N], dp2[N], cost1[N], cost2[N], index[N], curind, node[N], l1[N], l2[N];
      |                                                                                          ^
In file included from /usr/include/string.h:432,
                 from /usr/include/c++/10/cstring:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:48,
                 from catdog.cpp:2:
/usr/include/strings.h:61:1: note: previous declaration 'const char* index(const char*, int)'
   61 | index (const char *__s, int __c) __THROW
      | ^~~~~
catdog.cpp: In function 'void compute(int)':
catdog.cpp:124:8: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
  124 |   index[a] = ++curind;
      |        ^
catdog.cpp:125:13: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
  125 |   node[index[a]] = a;
      |             ^
catdog.cpp: In function 'void updVertex(int)':
catdog.cpp:143:21: error: invalid types '<unresolved overloaded function type>[int]' for array subscript
  143 |   upd(1, 0, n, index[v]);
      |                     ^
catdog.cpp:145:30: error: invalid types '<unresolved overloaded function type>[__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}]' for array subscript
  145 |   l1[color[v]] = getdp1(index[members[color[v]][0]], index[members[color[v]].back()]);
      |                              ^
catdog.cpp:145:59: error: invalid types '<unresolved overloaded function type>[__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}]' for array subscript
  145 |   l1[color[v]] = getdp1(index[members[color[v]][0]], index[members[color[v]].back()]);
      |                                                           ^
catdog.cpp:146:30: error: invalid types '<unresolved overloaded function type>[__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}]' for array subscript
  146 |   l2[color[v]] = getdp2(index[members[color[v]][0]], index[members[color[v]].back()]);
      |                              ^
catdog.cpp:146:59: error: invalid types '<unresolved overloaded function type>[__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}]' for array subscript
  146 |   l2[color[v]] = getdp2(index[members[color[v]][0]], index[members[color[v]].back()]);
      |                                                           ^
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from catdog.cpp:2:
catdog.cpp: In function 'void update(int)':
catdog.cpp:161:19: error: invalid types '<unresolved overloaded function type>[__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}]' for array subscript
  161 |       assert(index[members[color[node]][j - 1]] == index[members[color[node]][j]] - 1);
      |                   ^
catdog.cpp:161:57: error: invalid types '<unresolved overloaded function type>[__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}]' for array subscript
  161 |       assert(index[members[color[node]][j - 1]] == index[members[color[node]][j]] - 1);
      |                                                         ^
catdog.cpp:166:26: error: invalid types '<unresolved overloaded function type>[__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}]' for array subscript
  166 |     int i1 = getdp1(index[members[color[node]][0]], index[members[color[node]].back()]), i2 = getdp2(index[members[color[node]][0]], index[members[color[node]].back()]);
      |                          ^
catdog.cpp:166:58: error: invalid types '<unresolved overloaded function type>[__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}]' for array subscript
  166 |     int i1 = getdp1(index[members[color[node]][0]], index[members[color[node]].back()]), i2 = getdp2(index[members[color[node]][0]], index[members[color[node]].back()]);
      |                                                          ^
catdog.cpp:166:9: warning: unused variable 'i1' [-Wunused-variable]
  166 |     int i1 = getdp1(index[members[color[node]][0]], index[members[color[node]].back()]), i2 = getdp2(index[members[color[node]][0]], index[members[color[node]].back()]);
      |         ^~