| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 64832 | TadijaSebez | Cats or Dogs (JOI18_catdog) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 Set(int &c, int ss, int se, int qi, int a, int b)
{
if(!c) c=++tsz,node[c].init();
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);
}
void initialize(int n, int a[], int b[])
{
int i;
for(i=0;i<n-1;i++) E[a[i]].pb(b[i]),E[b[i]].pb(a[i]);
DFS(1,0);
HLD(1,0);
node[0].init();
}
int Solve(){ pair<int,int> sol=Get(root[1]);return min(sol.first,sol.second);}
int t[N];
void Set(int u, int a, int b)
{
while(u)
{
int pa,pb,na,nb;
pair<int,int> tmp=Get(root[head[u]]);
pa=tmp.first;pb=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-pa;b=nb-pb;
u=par[head[u]];
}
}
int cat(int u){ t[u]=1;Set(u,0,N);return Solve();}
int dog(int u){ t[u]=2;Set(u,N,0);return Solve();}
int neighbor(int u)
{
if(t[u]==1) Set(u,0,-N);
else Set(u,-N,0);
t[u]=0;
return Solve();
}