Submission #97804

#	Time	Username	Problem	Language	Result	Execution time	Memory
97804		fefe	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	2721 ms	29824 KiB

catdog

#include "catdog.h"
#include<bits/stdc++.h>
#define MAX_N 200005
#define MAX_M 100005
#define pb push_back
#define mp make_pair
#define all(V) (V).begin(),(V).end()
#define reset(V) (V).clear();(V).resize(0);
#define sq(x) ((x)*(x))
#define abs(x) ((x)>0?(x):(-(x)))
#define fi first
#define se second
#define LL_inf (1LL<<60)
#define full_inf 0x7fffffff
#define half_inf 0x3fffffff
#define inf 1000005
#define MOD 1000000007LL
#define cpx_mod(x) (((LD)(((LL)x.real())%MOD)),((LD)(((LL)x.imag())%MOD)))
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,LL> pil;
typedef pair<LL,string> pls;
typedef complex<LD> Complex;
typedef long double LD;
int x;
struct node{
	int cost[4];
}tree[4*MAX_N];
int n,m;
int num[MAX_N],sta[MAX_N],cnt[MAX_N],pa[MAX_N],C[MAX_N],D[MAX_N];
bool vis[MAX_N];
vector<int> E[MAX_N],lst[MAX_N];
void make_HLD(int x){
	cnt[x]=1;
	if(x!=1 && E[x].size()==1){
		E[x][0]=0;
		lst[m].pb(x);
		num[x]=m++;
		return;
	}
	int mi=0;
	for(int &y:E[x]){
		if(cnt[y]){y=0;continue;}
		make_HLD(y);pa[y]=x;
		cnt[x]+=cnt[y];
		if(cnt[y]>cnt[mi])	mi=y;
	}
	num[x]=num[mi];
	lst[num[x]].pb(x);
}
void init1(int x){for(int i=0;i<4;i++)	tree[x].cost[i]=(i%3?1:0)*inf;}
void initialize(int N, std::vector<int> A, std::vector<int> B) {
	cnt[0]=-1;
	n=N;
	for(int i=0;i<n-1;i++){
		E[A[i]].pb(B[i]);
		E[B[i]].pb(A[i]);
	}
	make_HLD(1);
	int x=n;
	for(int i=0;i<m;i++){
		for(int j:lst[i]){cnt[j]=x--;}
	}
	for(int i=1;i<=4*n;i++)	init1(i);
}
node merge(node x,node y){
	node p;
	for(int i=0;i<4;i++)	p.cost[i]=inf;
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++)	p.cost[(i/2)*2+j%2]=min(p.cost[(i/2)*2+j%2],x.cost[i]+y.cost[j]+((i%2)^(j/2)));
	}
	return p;
}
void udt_tree(int x,int l,int r,int p,node v){
	if(p<l || r<p)	return;
	if(l==r){
		tree[x]=v;
		return;
	}
	int mid=(l+r)>>1;
	udt_tree(2*x,l,mid,p,v);
	udt_tree(2*x+1,mid+1,r,p,v);
	tree[x]=merge(tree[2*x],tree[2*x+1]);
}
node get_cost(int x,int l,int r,int s,int e){
	if(e<l || s>r)	return {0,inf,inf,0};
	if(s<=l && r<=e)	return tree[x];
	int mid=(l+r)>>1;
	return merge(get_cost(2*x,l,mid,s,e),get_cost(2*x+1,mid+1,r,s,e));
}
void update(int x,int cat,int dog){
	if(!x)	return;
	int p=lst[num[x]].back();
	node q=get_cost(1,1,n,cnt[lst[num[x]].back()],cnt[lst[num[x]][0]]);
	C[pa[p]]-=min(min(q.cost[0],q.cost[1]),min(q.cost[2],q.cost[3])+1);
	D[pa[p]]-=min(min(q.cost[2],q.cost[3]),min(q.cost[0],q.cost[1])+1);
	udt_tree(1,1,n,cnt[x],{cat,inf,inf,dog});
	q=get_cost(1,1,n,cnt[lst[num[x]].back()],cnt[lst[num[x]][0]]);
	C[pa[p]]+=min(min(q.cost[0],q.cost[1]),min(q.cost[2],q.cost[3])+1);
	D[pa[p]]+=min(min(q.cost[2],q.cost[3]),min(q.cost[0],q.cost[1])+1);
	cat=(sta[pa[p]]==2)?inf:C[pa[p]];
	dog=(sta[pa[p]]==1)?inf:D[pa[p]];
	update(pa[p],cat,dog);
	return;
}
int get_min(){
	node p=get_cost(1,1,n,cnt[1],cnt[lst[num[1]][0]]);
	return min({p.cost[0],p.cost[1],p.cost[2],p.cost[3]});
}
int cat(int v){
	sta[v]=1;
	update(v,C[v],inf);
	return get_min();
}
int dog(int v){
	sta[v]=2;
	update(v,inf,D[v]);
	return get_min();
}
int neighbor(int v){
	sta[v]=0;
	update(v,C[v],D[v]);
	return get_min();
}

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