Submission #98373

#	Time	Username	Problem	Language	Result	Execution time	Memory
98373		scanhex	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	1640 ms	28920 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){
	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];

void update_c(int x,int coef){
	upd(ind[x]);
	vector<int>memos;
	while(true){
		x=top[x];
		if(x==0)break;
		memos.push_back(x);
		x=par[x];
	}
	if(coef==-1)reverse(memos.begin(),memos.end());
	for(int x:memos){
		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]);
		if(k0>=oo&&k1>=oo){
			int aoeustnaoeu=22390;
		}
		assert(k0<oo||k1<oo);
		t[y][0][0]+=coef*(min(k0,k1+1));
		t[y][1][1]+=coef*(min(k1,k0+1));
		upd(ind[x]);
	}
}

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){
	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);
	fill(cur,cur+n,3);
	d1(0);
	d2(0);
	d3(0);
}

int get(){
	val mem=get(ind[0],ind[listok[0]]+1);
	int ans=oo;
	for(int i=0;i<2;++i)
		for(int j=0;j<2;++j)
			ans=min(ans,mem[i][j]);
	return ans;
}

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

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

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

Compilation message (stderr)

catdog.cpp: In function 'void update_c(int, int)':
catdog.cpp:92:8: warning: unused variable 'aoeustnaoeu' [-Wunused-variable]
    int aoeustnaoeu=22390;
        ^~~~~~~~~~~

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