Submission #92585

#	Time	Username	Problem	Language	Result	Execution time	Memory
92585		Bodo171	Cats or Dogs (JOI18_catdog)	C++14	0 / 100	6 ms	5880 KiB

catdog

#include "catdog.h"
#include <iostream>
using namespace std;
const int nmax=100005;
vector<int> v[nmax];
int wh[nmax],path[nmax],fail[nmax],w[nmax],big[nmax],ce[nmax],E[nmax];
long long sum_sons[nmax][3];
int aux[5];
int x,n,paths;
struct mat
{
    int m[3][3];
}zr,mare;
void mrg(mat &A,mat B,mat C)
{
    for(int i1=0;i1<3;i1++)
      for(int i2=0;i2<3;i2++)
         A.m[i1][i2]=2*n;
    for(int i1=0;i1<3;i1++)
        for(int m1=0;m1<3;m1++)
           for(int m2=0;m2<3;m2++)
             for(int i2=0;i2<3;i2++)
                A.m[i1][i2]=min(A.m[i1][i2],B.m[i1][m1]+C.m[m2][i2]+(m1!=m2));
    for(int i1=0;i1<3;i1++)
        for(int i2=0;i2<3;i2++)
    {
        A.m[i1][i2]=min(A.m[i1][i2],B.m[0][0]+C.m[i1][i2]);
        A.m[i1][i2]=min(A.m[i1][i2],B.m[i1][i2]+C.m[0][0]);
    }
}
struct path
{
    int nodes;
    vector<mat> arb;
    void ins(int x)
    {
        wh[x]=++nodes;
    }
    void ini()
    {
        arb.resize(2*nodes+50);
        for(int idx=0;idx<arb.size();idx++)
            arb[idx]=mare;
    }
    void update(int nod,int l,int r,int x,int val)
    {
        if(l==r)
        {
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                  arb[nod].m[i][j]=2*n;
            long long t;
            t=min(sum_sons[x][val],1LL*2*n);
            arb[nod].m[val][val]=t;
            if(val==0)
            {
                for(int i=1;i<2;i++)
                {
                    t=min(sum_sons[x][i],1LL*2*n);
                    arb[nod].m[i][i]=t;
                }
            }
            for(int i=0;i<3;i++)
            {
                t=min(sum_sons[x][i]+1,1LL*2*n);
                arb[nod].m[val][val]=min(arb[nod].m[val][val],(int) t);
            }
            return;
        }
        int m=(l+r)/2;
        if(wh[x]<=m) update(2*nod,l,m,x,val);
        else update(2*nod+1,m+1,r,x,val);
        mrg(arb[nod],arb[2*nod],arb[2*nod+1]);
    }

    int mincost()
    {
        int ret=2*n;
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
               ret=min(ret,arb[1].m[i][j]);
       return ret;
    }
}P[nmax];
int min_lin(mat cv,int wh)
{
    int ret=2*n;
    for(int i=0; i<3; i++)
        ret=min(ret,cv.m[wh][i]);
    return ret;
}
void dfs(int x)
{
    w[x]=1;
    for(int i=0;i<v[x].size();i++)
        if(!w[v[x][i]])
    {
        dfs(v[x][i]);
        w[x]+=w[v[x][i]];
        if(w[v[x][i]]>w[big[x]])
        {
            big[x]=v[x][i];
        }
    }
    if(!big[x]) path[x]=++paths;
    else path[x]=path[big[x]];
    P[path[x]].ins(x);
    for(int i=0;i<v[x].size();i++)
        if(v[x][i]!=big[x])
    {
        fail[path[v[x][i]]]=x;
    }
}
void upd(int x,int val)
{
    int unde=0;
    ce[x]=val;
    while(x)
    {
        unde=path[x];
        for(int i=0;i<3;i++)
            aux[i]=0;
        if(E[path[x]])
         for(int i=0;i<3;i++)
           aux[i]=min_lin(P[unde].arb[1],i);
        E[path[x]]=1;
        P[path[x]].update(1,1,P[path[x]].nodes,x,ce[x]);
        for(int i=0;i<3;i++)
           aux[i]=min_lin(P[unde].arb[1],i)-aux[i];
        x=fail[path[x]];
        for(int i=0;i<3;i++)
            sum_sons[x][i]+=aux[i];
    }
}
void initialize(int N, vector<int> A, vector<int> B) {
  x = A.size();n=N;
  for(int i=0;i<N-1;i++)
  {
      v[A[i]].push_back(B[i]);
      v[B[i]].push_back(A[i]);
  }
  for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
      mare.m[i][j]=2*n;
  dfs(1);
  for(int i=1;i<=paths;i++)
    P[i].ini();
  for(int nod=1;nod<=n;nod++)
    upd(nod,0);
}

int cat(int v) {
  upd(v,1);
  return P[path[1]].mincost();
}

int dog(int v) {
  upd(v,2);
  return P[path[1]].mincost();
}

int neighbor(int v) {
  upd(v,0);
  return P[path[1]].mincost();
}

Compilation message (stderr)

catdog.cpp: In member function 'void path::ini()':
catdog.cpp:42:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int idx=0;idx<arb.size();idx++)
                       ~~~^~~~~~~~~~~
catdog.cpp: In function 'void dfs(int)':
catdog.cpp:95:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
catdog.cpp:108:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~

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