oj.uz

Submission #92599

# Submission time Handle Problem Language Result Execution time Memory
92599 2019-01-03T20:54:09 Z Bodo171 Cats or Dogs (JOI18_catdog) C++14
8 / 100
 8 ms 6264 KB 
#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];
int sum_sons[nmax][2];
int aux[5],value[5];
int x,n,paths;
struct mat
{
    int m[2][2];
}zr,mare;
void mrg(mat &A,mat B,mat C)
{
    for(int i1=0;i1<2;i1++)
      for(int i2=0;i2<2;i2++)
         A.m[i1][i2]=2*n;
    for(int i1=0;i1<2;i1++)
        for(int m1=0;m1<2;m1++)
           for(int m2=0;m2<2;m2++)
             for(int i2=0;i2<2;i2++)
                    A.m[i1][i2]=min(A.m[i1][i2],B.m[i1][m1]+C.m[m2][i2]+(m1^m2));
}
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<2;i++)
                for(int j=0;j<2;j++)
                  arb[nod].m[i][j]=2*n;
            if(val==2)
            {
                arb[nod].m[0][0]=sum_sons[x][0];
                arb[nod].m[1][1]=sum_sons[x][1];
            }
            else
            {
                arb[nod].m[val][val]=sum_sons[x][val];
            }
            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<2;i++)
            for(int j=0;j<2;j++)
               ret=min(ret,arb[1].m[i][j]);
       return ret;
    }
}P[nmax];
int min_col(mat cv,int wh)
{
    int ret=2*n;
    for(int ii=0; ii<2; ii++)
        ret=min(ret,cv.m[ii][wh]);
    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<2;i++)
            aux[i]=0;
        if(E[path[x]])
         for(int i=0;i<2;i++)
           aux[i]=min_col(P[unde].arb[1],i);
        aux[0]=min(aux[1]+1,aux[0]);
        aux[1]=min(aux[0]+1,aux[1]);
        E[path[x]]=1;
        P[path[x]].update(1,1,P[path[x]].nodes,x,ce[x]);

        for(int i=0;i<2;i++)
           value[i]=min_col(P[unde].arb[1],i);
        value[0]=min(value[1]+1,value[0]);
        value[1]=min(value[0]+1,value[1]);
        x=fail[path[x]];
        for(int i=0;i<2;i++)
            sum_sons[x][i]+=value[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<2;i++)
    for(int j=0;j<2;j++)
      mare.m[i][j]=2*n;
  dfs(1);
  for(int i=1;i<=paths;i++)
    P[i].ini();
  for(int i=1;i<=n;i++)
    ce[i]=2;
  for(int nod=1;nod<=n;nod++)
    upd(nod,2);
}

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

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

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

Compilation message

catdog.cpp: In member function 'void path::ini()':
catdog.cpp:36: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:82:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~
catdog.cpp:95:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[x].size();i++)
                 ~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5880 KB Output is correct
2 Correct 6 ms 5880 KB Output is correct
3 Correct 6 ms 5880 KB Output is correct
4 Correct 6 ms 5884 KB Output is correct
5 Correct 6 ms 5880 KB Output is correct
6 Correct 6 ms 5884 KB Output is correct
7 Correct 6 ms 5880 KB Output is correct
8 Correct 6 ms 5880 KB Output is correct
9 Correct 6 ms 5880 KB Output is correct
10 Correct 6 ms 5880 KB Output is correct
11 Correct 6 ms 5888 KB Output is correct
12 Correct 6 ms 5880 KB Output is correct
13 Correct 6 ms 5880 KB Output is correct
14 Correct 6 ms 5752 KB Output is correct
15 Correct 6 ms 5880 KB Output is correct
16 Correct 6 ms 5880 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5880 KB Output is correct
2 Correct 6 ms 5880 KB Output is correct
3 Correct 6 ms 5880 KB Output is correct
4 Correct 6 ms 5884 KB Output is correct
5 Correct 6 ms 5880 KB Output is correct
6 Correct 6 ms 5884 KB Output is correct
7 Correct 6 ms 5880 KB Output is correct
8 Correct 6 ms 5880 KB Output is correct
9 Correct 6 ms 5880 KB Output is correct
10 Correct 6 ms 5880 KB Output is correct
11 Correct 6 ms 5888 KB Output is correct
12 Correct 6 ms 5880 KB Output is correct
13 Correct 6 ms 5880 KB Output is correct
14 Correct 6 ms 5752 KB Output is correct
15 Correct 6 ms 5880 KB Output is correct
16 Correct 6 ms 5880 KB Output is correct
17 Correct 7 ms 6136 KB Output is correct
18 Correct 8 ms 6264 KB Output is correct
19 Correct 7 ms 6132 KB Output is correct
20 Correct 6 ms 6008 KB Output is correct
21 Correct 6 ms 5880 KB Output is correct
22 Correct 6 ms 6008 KB Output is correct
23 Correct 7 ms 6136 KB Output is correct
24 Correct 7 ms 6136 KB Output is correct
25 Correct 7 ms 6008 KB Output is correct
26 Correct 6 ms 6008 KB Output is correct
27 Incorrect 6 ms 5880 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5880 KB Output is correct
2 Correct 6 ms 5880 KB Output is correct
3 Correct 6 ms 5880 KB Output is correct
4 Correct 6 ms 5884 KB Output is correct
5 Correct 6 ms 5880 KB Output is correct
6 Correct 6 ms 5884 KB Output is correct
7 Correct 6 ms 5880 KB Output is correct
8 Correct 6 ms 5880 KB Output is correct
9 Correct 6 ms 5880 KB Output is correct
10 Correct 6 ms 5880 KB Output is correct
11 Correct 6 ms 5888 KB Output is correct
12 Correct 6 ms 5880 KB Output is correct
13 Correct 6 ms 5880 KB Output is correct
14 Correct 6 ms 5752 KB Output is correct
15 Correct 6 ms 5880 KB Output is correct
16 Correct 6 ms 5880 KB Output is correct
17 Correct 7 ms 6136 KB Output is correct
18 Correct 8 ms 6264 KB Output is correct
19 Correct 7 ms 6132 KB Output is correct
20 Correct 6 ms 6008 KB Output is correct
21 Correct 6 ms 5880 KB Output is correct
22 Correct 6 ms 6008 KB Output is correct
23 Correct 7 ms 6136 KB Output is correct
24 Correct 7 ms 6136 KB Output is correct
25 Correct 7 ms 6008 KB Output is correct
26 Correct 6 ms 6008 KB Output is correct
27 Incorrect 6 ms 5880 KB Output isn't correct
28 Halted 0 ms 0 KB -