#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));
if((m1==0&&i1!=0)||(m2==0&&i2!=0))
{
A.m[i1][i2]=min(A.m[i1][i2],B.m[i1][m1]+C.m[m2][i2]);
}
}
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
catdog.cpp: In member function 'void path::ini()':
catdog.cpp:48: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:101:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
catdog.cpp:114:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5880 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
5880 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5880 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
5880 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5880 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
5880 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
