Submission #118413

#	Time	Username	Problem	Language	Result	Execution time	Memory
118413		kig9981	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	743 ms	21880 KiB

catdog

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

using namespace std;

const int SZ=1<<17;
vector<int> adj[100000];
int N, parent[100000], W[100000], num[100000], R[100000], hld[100000], V[100000], tree[2*SZ][4];

void add_tree(int n, int v1, int v2)
{
	n+=SZ;
	tree[n][0]+=v1; tree[n][3]+=v2;
	while(n>>=1) {
		for(int i=0;i<4;i++) tree[n][i]=0x1fffffff;
		for(int i=0;i<4;i++) for(int j=0;j<4;j++) tree[n][(i&2)|(j&1)]=min(tree[n][(i&2)|(j&1)],tree[2*n][i]+tree[2*n+1][j]+((i&1)^(j>>1)));
	}
}

void get_ans(int *ret, int s, int e)
{
	int r1[4]={0,0x1fffffff,0x1fffffff,0}, r2[4]={0,0x1fffffff,0x1fffffff,0};
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) {
			for(int i=0;i<4;i++) ret[i]=0x1fffffff;
			for(int i=0;i<4;i++) for(int j=0;j<4;j++) ret[(i&2)|(j&1)]=min(ret[(i&2)|(j&1)],r1[i]+tree[s][j]+((i&1)^(j>>1)));
			for(int i=0;i<4;i++) r1[i]=ret[i];
			s++;
		}
		if(~e&1) {
			for(int i=0;i<4;i++) ret[i]=0x1fffffff;
			for(int i=0;i<4;i++) for(int j=0;j<4;j++) ret[(i&2)|(j&1)]=min(ret[(i&2)|(j&1)],tree[e][i]+r2[j]+((i&1)^(j>>1)));
			for(int i=0;i<4;i++) r2[i]=ret[i];
			e--;
		}
	}
	for(int i=0;i<4;i++) ret[i]=0x1fffffff;
	for(int i=0;i<4;i++) for(int j=0;j<4;j++) ret[(i&2)|(j&1)]=min(ret[(i&2)|(j&1)],r1[i]+r2[j]+((i&1)^(j>>1)));
}

int dfs(int c)
{
	W[c]=1;
	for(auto n: adj[c]) if(W[n]==0) {
		parent[n]=c;
		W[c]+=dfs(n);
	}
	return W[c];
}

int dfs2(int c)
{
	num[c]=R[c]=N++;
	for(auto n: adj[c]) if(parent[n]==c && 2*W[n]>=W[c]) {
		hld[n]=hld[c];
		R[c]=dfs2(n);
	}
	for(auto n: adj[c]) if(parent[n]==c && 2*W[n]<W[c]) {
		hld[n]=n;
		dfs2(n);
	}
	return R[c];
}

void initialize(int N, vector<int> A, vector<int> B)
{
	for(int i=0;i<N-1;i++) {
		adj[--A[i]].push_back(--B[i]);
		adj[B[i]].push_back(A[i]);
		tree[SZ+i][1]=tree[SZ+i][2]=N;
	}
	tree[SZ+N-1][1]=tree[SZ+N-1][2]=N;
	dfs(0); dfs2(0);
	for(int n=SZ-1;n;n--) {
		for(int i=0;i<4;i++) tree[n][i]=0x1fffffff;
		for(int i=0;i<4;i++) for(int j=0;j<4;j++) tree[n][(i&2)|(j&1)]=min(tree[n][(i&2)|(j&1)],tree[2*n][i]+tree[2*n+1][j]+((i&1)^(j>>1)));
	}
}

int cat(int c)
{
	int t1[4], t2[4], v1=0, v2=N;
	V[--c]=1;
	for(;;) {
		get_ans(t1,num[hld[c]],R[c]);
		add_tree(num[c],v1,v2);
		get_ans(t2,num[hld[c]],R[c]);
		if(hld[c]==0) break;
		t1[0]=min(t1[0],t1[1]); t1[1]=min(t1[2],t1[3]);
		t2[0]=min(t2[0],t2[1]); t2[1]=min(t2[2],t2[3]);
		v1=min(t2[0],t2[1]+1)-min(t1[0],t1[1]+1);
		v2=min(t2[0]+1,t2[1])-min(t1[0]+1,t1[1]);
		c=parent[hld[c]];
		if(v1==0 && v2==0) {
			get_ans(t2,num[0],R[0]);
			break;
		}
	}
	return min({t2[0],t2[1],t2[2],t2[3]});
}

int dog(int c)
{
	int t1[4], t2[4], v1=N, v2=0;
	V[--c]=2;
	for(;;) {
		get_ans(t1,num[hld[c]],R[c]);
		add_tree(num[c],v1,v2);
		get_ans(t2,num[hld[c]],R[c]);
		if(hld[c]==0) break;
		t1[0]=min(t1[0],t1[1]); t1[1]=min(t1[2],t1[3]);
		t2[0]=min(t2[0],t2[1]); t2[1]=min(t2[2],t2[3]);
		v1=min(t2[0],t2[1]+1)-min(t1[0],t1[1]+1);
		v2=min(t2[0]+1,t2[1])-min(t1[0]+1,t1[1]);
		c=parent[hld[c]];
		if(v1==0 && v2==0) {
			get_ans(t2,num[0],R[0]);
			break;
		}
	}
	return min({t2[0],t2[1],t2[2],t2[3]});
}

int neighbor(int c)
{
	c--;
	int t1[4], t2[4], v1=-N*(V[c]==2), v2=-N*(V[c]==1);
	V[c]=0;
	for(;;) {
		get_ans(t1,num[hld[c]],R[c]);
		add_tree(num[c],v1,v2);
		get_ans(t2,num[hld[c]],R[c]);
		if(hld[c]==0) break;
		t1[0]=min(t1[0],t1[1]); t1[1]=min(t1[2],t1[3]);
		t2[0]=min(t2[0],t2[1]); t2[1]=min(t2[2],t2[3]);
		v1=min(t2[0],t2[1]+1)-min(t1[0],t1[1]+1);
		v2=min(t2[0]+1,t2[1])-min(t1[0]+1,t1[1]);
		c=parent[hld[c]];
		if(v1==0 && v2==0) {
			get_ans(t2,num[0],R[0]);
			break;
		}
	}
	return min({t2[0],t2[1],t2[2],t2[3]});
}

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