Submission #536499

#	Time	Username	Problem	Language	Result	Execution time	Memory
536499		cadmiumsky	Cats or Dogs (JOI18_catdog)	C++14	0 / 100	5 ms	8916 KiB

catdog

#include <bits/stdc++.h>
#include "catdog.h"
using namespace std;
const int nmax = 1e5 + 5, qmax = 1e5 + 5, inf = 1e8 + 8;
#define red first
#define blue second
#define pii pair<int,int>
// -1 -- insipid, 0 -- rosu, 1 -- albastru 
int n;
vector<int> g[nmax];
namespace HLD {
  namespace AINT {
    struct Mat {
      int dp[2][2];
      #warning poate pica memset
      Mat() {dp[0][0] = dp[1][1] = 0, dp[0][1] = dp[1][0] = inf;} 
      Mat(int _00, int _11) {
        dp[0][0] = _00;
        dp[1][1] = _11;
        dp[0][1] = inf;
        dp[1][0] = inf;
      }
      Mat(int _00, int _01, int _10, int _11) {
        dp[0][0] = _00;
        dp[0][1] = _01;
        dp[1][0] = _10;
        dp[1][1] = _11;
      }
      Mat operator + (const Mat& x) const {
        Mat rez;
        for(int l = 0; l < 2; l++)
          for(int r = 0; r < 2; r++) {
            rez.dp[l][r] = inf;
            for(int i = 0; i < 2; i++)
              for(int j = 0; j < 2; j++)
                rez.dp[l][r] = min(rez.dp[l][r], dp[l][i] + x.dp[j][r] + (i ^ j));
          }
        return rez;
      }
    };
    Mat aint[nmax * 4];
    void upd(int poz, int l, int r, int node = 1, int cl = 1, int cr = n) {
      if(cl == cr) {
        aint[node] = Mat(l, r);
        return;
      }
      int mid = cl + cr >> 1;
      if(poz <= mid) 
        upd(poz, l, r, 2 * node, cl, mid);
      else
        upd(poz, l, r, 2 * node + 1, mid + 1, cr);
      aint[node] = aint[2 * node] + aint[2 * node + 1];
      //cout << '\t' << cl << ' ' << cr <<'\n';
      auto rez = aint[node];
       //cout << "\t>  " << rez.dp[0][0] << ' ' << rez.dp[0][1] << "\n\t>  " << rez.dp[1][0] << ' ' << rez.dp[1][1] << '\n';
     
      return;
    }
    Mat GetQuery(int l, int r, int node = 1, int cl = 1, int cr = n) {
      if(r < cl || cr < l)
        return Mat();
      if(l <= cl && cr <= r)
        return aint[node];
      int ok = 0, mid = cl + cr >> 1;
      Mat rez;
      if(l <= mid)
        rez = GetQuery(l, r, 2 * node ,cl, mid), ok = 1;
      if(mid < r) 
        if(ok)
          rez = rez + GetQuery(l, r, 2 * node + 1, mid + 1, cr);
        else
          rez = GetQuery(l, r, 2 * node + 1, mid + 1, cr);
      return rez;
    }
    pii query(int l, int r) {
      Mat rez = GetQuery(l, r);
      //cout << l << ' ' << r << '\n';
      //cout << ">  " << rez.dp[0][0] << ' ' << rez.dp[0][1] << "\n>  " << rez.dp[1][0] << ' ' << rez.dp[1][1] << '\n';
      return {min(rez.dp[0][0], rez.dp[0][1]),
              min(rez.dp[1][0], rez.dp[1][1])};
    }
  }
  int p[nmax], preord[nmax], pin[nmax], lch[nmax], rch[nmax], atrch[nmax], inp = 1, inch = 0;
  int area[nmax];
  void initarea(int node, int f = 1) {
    area[node] = 1;
    atrch[node] = rch[node - 1] = 0;
    lch[node - 1] = inf; 
    p[node] = f;
    for(auto x : g[node]) {
      if(x != f)
        initarea(x, node), area[node] += area[x];
    }
  }
  void initdfs(int node, int f = 1) {
    atrch[node] = inch;
    lch[inch] = min(inp, lch[inch]); 
    rch[inch] = max(inp, rch[inch]);
    pin[node] = inp, preord[node] = inp++;
    //cout << node << ' ' << pin[node] << ' ' << inch << '\t' << lch[inch] << ' ' << rch[inch]<< '\n';
    if(node != f && g[node].size() == 1)
      return;
    vector<int> son;
    for(auto x : g[node]) {
      if(x == f)
        continue;
      son.push_back(x);
    }
    sort(son.begin(), son.end(), [&](auto x, auto y){return area[x] < area[y];});
    initdfs(son.back(), node);
    son.pop_back();
    for(auto x : son) {
      inch++;
      initdfs(x, node);
    }
  }
  int fch(int ch) {
    return preord[lch[ch]];
  }
  int color[nmax];
  pii sons[nmax], dp[nmax], total[nmax];
  int gotop(int u) {
    int ch = atrch[u];
    dp[u] = sons[u];
    if(color[u] == 0)
      dp[u].blue = inf;
    else if(color[u] == 1)
      dp[u].red = inf;
    //cout << u << ' ' << dp[u].red << ' ' << dp[u].blue << '\n';
    AINT::upd(pin[u], dp[u].red, dp[u].blue);
    pii rez = AINT::query(lch[ch], rch[ch]);
    //cout << rez.red << ' ' << rez.blue << '\n';
    if(ch == 0)
      return min(rez.red, rez.blue);
    u = fch(ch);
    int f = p[u];
    sons[f].red -= min(total[u].red, total[u].blue + 1), sons[f].blue -= min(total[u].red + 1, total[u].blue);
    sons[f].red += min(rez.red, rez.blue + 1), sons[f].blue += min(rez.red + 1, rez.blue);
    return gotop(f);
  }
  int setcolor(int u, int x) {
    color[u] = x;
    return gotop(u);
  }
}


void initialize(int N, std::vector<int> A, std::vector<int> B) {
  n = N;
  for(int i = 0; i < N - 1; i++)
    g[A[i]].push_back(B[i]),
    g[B[i]].push_back(A[i]);
  HLD::initarea(1);
  HLD::initdfs(1);
}

int cat(int v) {
  return HLD::setcolor(v, 0);
}

int dog(int v) {
  return HLD::setcolor(v, 1);
}

int neighbor(int v) {
  return HLD::setcolor(v, -1);
}

Compilation message (stderr)

catdog.cpp:15:8: warning: #warning poate pica memset [-Wcpp]
   15 |       #warning poate pica memset
      |        ^~~~~~~
catdog.cpp: In function 'void HLD::AINT::upd(int, int, int, int, int, int)':
catdog.cpp:47:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |       int mid = cl + cr >> 1;
      |                 ~~~^~~~
catdog.cpp:54:12: warning: variable 'rez' set but not used [-Wunused-but-set-variable]
   54 |       auto rez = aint[node];
      |            ^~~
catdog.cpp: In function 'HLD::AINT::Mat HLD::AINT::GetQuery(int, int, int, int, int)':
catdog.cpp:64:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |       int ok = 0, mid = cl + cr >> 1;
      |                         ~~~^~~~
catdog.cpp:68:9: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   68 |       if(mid < r)
      |         ^

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