Submission #491899

#	Time	Username	Problem	Language	Result	Execution time	Memory
491899		ivan_tudor	Cats or Dogs (JOI18_catdog)	C++14	38 / 100	3070 ms	12656 KiB

catdog

#include "catdog.h"
using namespace std;
const int N = 100005;
vector<int> gr[N];
int par[N];
int root = 1;
int t[N];
int nr[3][N];
int col[N];
int ans;
void dfs_init(int nod, int dad){
  par[nod] = dad;
  for(auto x:gr[nod]){
    if(x == dad)
      continue;
    dfs_init(x, nod);
  }
  t[nod] = nr[0][nod] = nr[1][nod] = nr[2][nod] = 0;
  col[nod] = 0;
}
void initialize(int N, std::vector<int> A, std::vector<int> B){
  for(int i = 0; i < N - 1; i++){
    gr[A[i]].push_back(B[i]);
    gr[B[i]].push_back(A[i]);
  }
  dfs_init(root, 0);
  ans = 0;
};
int other(int tip){
  if(tip == 1)
    return 2;
  if(tip == 2)
    return 1;
  return 1;
}
void update_son(int nod, int oldtson, int newtson){
  if(nod == 0)
    return;
  if(oldtson == newtson)
    return;

  if(col[nod] != 0){
    nr[oldtson][nod] --;
    if(oldtson == other(col[nod]))
      ans--;
    nr[newtson][nod] ++;
    if(newtson == other(col[nod]))
      ans++;
    return;
  }

  int oldtip = t[nod];
  if(oldtip == 0)
    ans -= min(nr[1][nod], nr[2][nod]);
  else
    ans -= nr[other(oldtip)][nod];
  nr[oldtson][nod] --;
  nr[newtson][nod] ++;
  if(nr[1][nod] < nr[2][nod]){
    ans += nr[1][nod];
    t[nod] = 2;
  }
  else if(nr[2][nod] < nr[1][nod]){
    ans += nr[2][nod];
    t[nod] = 1;
  }
  else{
    t[nod] = 0;
    ans += nr[1][nod];
  }
  if(oldtip == t[nod])
    return;
  update_son(par[nod], oldtip, t[nod]);
}
void update(int nod, int cl){
  if(col[nod] == cl)
    return;
  // sterg ce era inainte

  int oldtip = t[nod];
  if(col[nod] == 0)
    ans -= min(nr[1][nod], nr[2][nod]);
  else
    ans -= nr[other(col[nod])][nod];
  col[nod] = cl; // pun culoarea noua
  if(cl != 0){
    t[nod] = cl;
    ans += nr[other(cl)][nod];
  }
  else{
    if(nr[1][nod] < nr[2][nod]){
      ans += nr[1][nod];
      t[nod] = 2;
    }
    else if(nr[2][nod] < nr[1][nod]){
      ans += nr[2][nod];
      t[nod] = 1;
    }
    else{
      t[nod] = 0;
      ans += nr[1][nod];
    }
  }
  if(oldtip == t[nod])
    return;
  update_son(par[nod], oldtip, t[nod]);
}
int cat(int v){
  update(v, 1);
  return ans;
}
int dog(int v){
  update(v, 2);
  return ans;
}
int neighbor(int v){
  update(v, 0);
  return ans;
}

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