Submission #64841

#	Time	Username	Problem	Language	Result	Execution time	Memory
64841		TadijaSebez	Cats or Dogs (JOI18_catdog)	C++11	100 / 100	451 ms	74724 KiB

catdog

#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;
	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++) if(E[u][i]!=p) DFS(E[u][i],u),sz[u]+=sz[E[u][i]];
}
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]=head[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)
{
	for(int i=0;i<n-1;i++) E[a[i]].pb(b[i]),E[b[i]].pb(a[i]);
	DFS(1,0);HLD(1,0);
}
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);
	return Solve();
}

Compilation message (stderr)

catdog.cpp: In function 'void Set(int&, int, int, int, int, int)':
catdog.cpp:34:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
catdog.cpp: In function 'void DFS(int, int)':
catdog.cpp:52:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<E[u].size();i++) if(E[u][i]!=p) DFS(E[u][i],u),sz[u]+=sz[E[u][i]];
              ~^~~~~~~~~~~~
catdog.cpp: In function 'void HLD(int, int)':
catdog.cpp:59: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:61: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);
          ~^~~~~~~~~~~~

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