#include "catdog.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define mp make_pair
#define pb push_back
const int inf=1e9+7;
int min(int a, int b){ return a>b?b:a;}
const int N=100050;
const int M=2*N;
struct Matrix
{
int a[2][2];
void init(){ a[0][0]=a[1][1]=0;a[1][0]=a[0][1]=inf;}
Matrix(){ init();}
Matrix operator * (Matrix b) const
{
Matrix c;
int i,j,k,l;
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
c.a[i][j]=inf;
for(k=0;k<2;k++)
{
for(l=0;l<2;l++)
{
c.a[i][j]=min(c.a[i][j],a[i][k]+b.a[l][j]+(k^l));
}
}
}
}
return c;
}
} node[M];
int ls[M],rs[M],root[N],tsz;
void Build(int &c, int ss, int se)
{
c=++tsz;
if(ss==se){ node[c].init();return;}
int mid=ss+se>>1;
Build(ls[c],ss,mid);
Build(rs[c],mid+1,se);
node[c]=node[ls[c]]*node[rs[c]];
}
void Set(int c, int ss, int se, int qi, int a, int b)
{
if(ss==se){ node[c].a[0][0]+=a;node[c].a[1][1]+=b;return;}
int mid=ss+se>>1;
if(qi<=mid) Set(ls[c],ss,mid,qi,a,b);
else Set(rs[c],mid+1,se,qi,a,b);
node[c]=node[ls[c]]*node[rs[c]];
}
pair<int,int> Get(int c)
{
int a=min(node[c].a[0][0],node[c].a[0][1]);
int b=min(node[c].a[1][0],node[c].a[1][1]);
a=min(a,b+1);
b=min(b,a+1);
return mp(a,b);
}
int head[N],sz[N],dep[N],par[N],csz[N];
vector<int> E[N];
void DFS(int u, int p)
{
par[u]=p;
dep[u]=dep[p]+1;
sz[u]=1;
for(int i=0;i<E[u].size();i++)
{
int v=E[u][i];
if(v!=p) DFS(v,u),sz[u]+=sz[v];
}
}
void HLD(int u, int p)
{
if(!head[u]) head[u]=u;
csz[head[u]]++;
int HC=0,i;
for(i=0;i<E[u].size();i++) if(E[u][i]!=p && sz[HC]<sz[E[u][i]]) HC=E[u][i];
if(HC) head[HC]=u;
for(i=0;i<E[u].size();i++) if(E[u][i]!=p) HLD(E[u][i],u);
}
int t[N];
void initialize(int n, vector<int> a, vector<int> b)
{
int i;
for(i=1;i<=n;i++) head[i]=root[i]=csz[i]=t[i]=0,E[i].clear();
for(i=0;i<n-1;i++) E[a[i]].pb(b[i]),E[b[i]].pb(a[i]);
for(i=1;i<=tsz;i++) ls[i]=rs[i]=0;
tsz=0;
DFS(1,0);
HLD(1,0);
node[0].init();
for(i=1;i<=n;i++) if(head[i]==i) Build(root[i],1,csz[i]);
}
int Solve(){ pair<int,int> sol=Get(root[1]);return min(sol.first,sol.second);}
void Set(int u, int a, int b)
{
while(u)
{
int la,lb,na,nb;
pair<int,int> tmp=Get(root[head[u]]);
la=tmp.first;lb=tmp.second;
Set(root[head[u]],1,csz[head[u]],dep[u]-dep[head[u]]+1,a,b);
tmp=Get(root[head[u]]);
na=tmp.first;nb=tmp.second;
a=na-la;b=nb-lb;
u=par[head[u]];
}
}
int cat(int u){ t[u]=1;Set(u,N,0);return Solve();}
int dog(int u){ t[u]=2;Set(u,0,N);return Solve();}
int neighbor(int u)
{
if(t[u]==1) Set(u,-N,0);
if(t[u]==2) Set(u,0,-N);
t[u]=0;
return Solve();
}
Compilation message
catdog.cpp: In function 'void Build(int&, int, int)':
catdog.cpp:43:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
catdog.cpp: In function 'void Set(int, int, int, int, int, int)':
catdog.cpp:51:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
catdog.cpp: In function 'void DFS(int, int)':
catdog.cpp:71:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<E[u].size();i++)
~^~~~~~~~~~~~
catdog.cpp: In function 'void HLD(int, int)':
catdog.cpp:82:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<E[u].size();i++) if(E[u][i]!=p && sz[HC]<sz[E[u][i]]) HC=E[u][i];
~^~~~~~~~~~~~
catdog.cpp:84:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<E[u].size();i++) if(E[u][i]!=p) HLD(E[u][i],u);
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5880 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
5992 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5880 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
5992 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
5880 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
5992 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
