Submission #98354

#	Time	Username	Problem	Language	Result	Execution time	Memory
98354		scanhex	Cats or Dogs (JOI18_catdog)	C++17	38 / 100	3007 ms	14588 KiB

catdog

#include<bits/stdc++.h>
#include "catdog.h"

using namespace std;
const int N=1<<17;
using val=array<array<int,2>,2>;
val t[2*N];

int par[N];
int cur[N];

#define chmi(x,y) if(x>y)x=y
#define chma(x,y) if(x<y)x=y

const int oo=100001;

int invind[N];

val gett(int x){
	if(x<N)
		return t[x];
	val ans;
	int u=invind[x-N];
	for(int i=0;i<2;++i)
		for(int j=0;j<2;++j)
			if(i==j&&((i+1)&cur[u]))
				ans[i][j]=t[x][i][j];
			else
				ans[i][j]=oo;
	return ans;
}

val merge(val a,val b){
	val ans;
	for(int st=0;st<2;++st)
		for(int en=0;en<2;++en){
			ans[st][en]=oo;
			for(int le=0;le<2;++le)
				for(int ri=0;ri<2;++ri){
					chmi(ans[st][en],a[st][le]+b[ri][en]+(le!=ri));
				}
		}
	return ans;
}

void upd1(int x){
//	if(x==(N+2)/2);
//	cerr<<"lul "<<gett(x<<1)[0][0]<<' '<<gett(x<<1^1)[0][0]<<'\n';
	t[x]=merge(gett(x<<1),gett(x<<1^1));
}

void upd(int x){
	x+=N;
	while(x>1)
		upd1(x>>1),x>>=1;
}
val neut={0,oo,oo,0};
val get(int l,int r){
	l+=N;
	r+=N;
	val ansle=neut,ansri=neut;
	while(l<r){
		if(l&1)
			ansle=merge(ansle,gett(l++));
		if(r&1)
			ansri=merge(gett(--r),ansri);
		l/=2,r/=2;
	}
	return merge(ansle,ansri);
}

vector<int> ch[N];
int ind[N];
int sz[N];
int top[N];
int listok[N];

/*
val vals[4];
void init_vals(){
	vals[1]={{0,oo},{oo,oo}};
	vals[2]={{oo,oo},{oo,0}};
	vals[3]={{0,oo},{oo,0}};
}
bool trash=(init_vals(),true);
*/

void update_c(int x,int coef){
	while(true){
		upd(ind[x]);
		x=top[x];
		if(x==0)break;
		val kek=get(ind[x],ind[listok[x]]+1);
		x=par[x];
		int y=ind[x]+N;
		int k0=min(kek[0][0],kek[0][1]),k1=min(kek[1][0],kek[1][1]);
		t[y][0][0]+=coef*(min(k0,k1+1));
		t[y][1][1]+=coef*(min(k1,k0+1));
	}
}

void update(int x,int nw){
	update_c(x,-1);
	cur[x]=nw;
	update_c(x,1);
}


vector<int>g[N];

void d1(int u,int p=-1){
	par[u]=p;
	sz[u]=1;
	for(int v:g[u]){
		if(v==p)continue;
		ch[u].push_back(v);
		d1(v,u);
		sz[u]+=sz[v];
		if(sz[v]>sz[ch[u][0]])
			swap(ch[u].back(),ch[u][0]);
	}
	if(ch[u].size())listok[u]=listok[ch[u][0]];
	else listok[u]=u;
}

int tot=0;


void d2(int u){
	ind[u]=tot++;
	invind[ind[u]]=u;
	for(int v:ch[u]){
		if(v==ch[u][0])
			top[v]=top[u];
		else
			top[v]=v;
		d2(v);
	}
}
void d3(int u){
	cur[u]=3;
	update_c(u,1);
	for(int v:ch[u])d3(v);
}

int n;

void initialize(int N1, std::vector<int> A, std::vector<int> B) {
	n=N1;
	for(int i=0;i<n-1;++i)
		g[A[i]-1].push_back(B[i]-1),g[B[i]-1].push_back(A[i]-1);
	d1(0);
	d2(0);
	d3(0);
}

int dp[N][2];
pair<int,int> calc(int u){
	pair<int,int>ans={oo,oo};
	if(cur[u]&1)ans.first=0;
	if(cur[u]&2)ans.second=0;
	for(int v:ch[u]){
		auto p=calc(v);
		ans.first+=min(p.first,p.second+1);
		ans.second+=min(p.first+1,p.second);
	}
	return ans;
}
int get(){
	auto p=calc(0);
	return min(p.first,p.second);
}

int cat(int v) {
	update(v-1,1);
	return get();
}

int dog(int v) {
	update(v-1,2);
	//for(int i=0;i<n;++i)
		//cerr<<gett((i+N)/1)[0][0]<<' '<<gett((i+N)/1)[1][1]<<'\n';
	//cerr<<'\n';
	return get();
}

int neighbor(int v) {
	update(v-1,3);
	return get();
}

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