Submission #1114901

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114901		PieArmy	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	1335 ms	25928 KiB

catdog

#include "catdog.h"
typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=100000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}

array<array<int,2>,2> comb(array<array<int,2>,2> a,array<array<int,2>,2> b){
	array<array<int,2>,2> res;
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			res[i][j]=min(min(a[i][0]+b[0][j],a[i][0]+b[1][j]+1),min(a[i][1]+b[0][j]+1,a[i][1]+b[1][j]));
		}
	}
	return res;
}
struct Seg{
	int n;
	vector<array<array<int,2>,2>>tree;
	void build(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			tree[node]={array<int,2>{0,sonsuz*2},array<int,2>{sonsuz*2,0}};
			return;
		}
		build(node*2,left,mid);
		build(node*2+1,mid+1,right);
		tree[node]=comb(tree[node*2],tree[node*2+1]);
	}
	void init(int N){
		n=N;
		tree.resize(n<<2, array<array<int,2>,2>{array<int,2>{0,0},array<int,2>{0,0}});
		build();
	}
	int l,r,c;
	void up(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left==right){
			tree[node][r][r]+=c;
			return;
		}
		if(l>mid)up(node*2+1,mid+1,right);
		else up(node*2,left,mid);
		tree[node]=comb(tree[node*2],tree[node*2+1]);
	}
	void update(int tar,int i,int val){
		l=tar;
		r=i;
		c=val;
		up();
	}
	array<array<int,2>,2> qu(int node=1,int left=0,int right=-1){
		if(right==-1)right=n-1;
		if(left>r||right<l)return array<array<int,2>,2>{array<int,2>{0,2*sonsuz},array<int,2>{2*sonsuz,0}};
		if(left>=l&&right<=r)return tree[node];
		return comb(qu(node*2,left,mid),qu(node*2+1,mid+1,right));
	}
	array<array<int,2>,2> query(int lef,int rig){
		l=lef;
		r=rig;
		return qu();
	}
};

int n;
int tim=0;
int tip[100001],par[100001],pre[100001],sub[100001],bas[100001],bottom[100001];
Seg seg;
vector<int>komsu[100001];

void dfs1(int pos){
	sub[pos]=1;
	for(int x:komsu[pos]){
		if(x==pre[pos])continue;
		pre[x]=pos;
		dfs1(x);
		sub[pos]+=sub[x];
	}
}

void dfs2(int pos){
	int mx=-1;
	bottom[par[pos]]=pos;
	bas[pos]=tim++;
	for(int x:komsu[pos]){
		if(x==pre[pos])continue;
		if(mx==-1||sub[mx]<sub[x])mx=x;
	}
	if(mx!=-1){
		par[mx]=par[pos];
		dfs2(mx);
		for(int x:komsu[pos]){
			if(x==mx||x==pre[pos])continue;
			par[x]=x;
			dfs2(x);
		}
	}
}

void initialize(int N,vector<int> A,vector<int> B){
	n=N;
	for(int i=0;i<n-1;i++){
		komsu[A[i]].pb(B[i]);
		komsu[B[i]].pb(A[i]);
	}
	par[1]=1;
	dfs1(1);
	dfs2(1);
	seg.init(tim);
}

void sil(int loc){
	if(pre[par[loc]]==0)return;
	sil(pre[par[loc]]);
	array<array<int,2>,2>sum=seg.query(bas[par[loc]],bas[bottom[par[loc]]]);
	seg.update(bas[pre[par[loc]]],0,-min(min(sum[0][0],sum[0][1]),min(sum[1][0],sum[1][1])+1));
	seg.update(bas[pre[par[loc]]],1,-min(min(sum[0][0],sum[0][1])+1,min(sum[1][0],sum[1][1])));
}

void op(int loc){
	array<array<int,2>,2>sum={array<int,2>{0,0},array<int,2>{0,0}};
	while(loc){
		seg.update(bas[loc],0,min(min(sum[0][0],sum[0][1]),min(sum[1][0],sum[1][1])+1));
		seg.update(bas[loc],1,min(min(sum[0][0],sum[0][1])+1,min(sum[1][0],sum[1][1])));
		sum=seg.query(bas[par[loc]],bas[bottom[par[loc]]]);
		loc=pre[par[loc]];
	}
}

int cat(int v){
	sil(v);
	seg.update(bas[v],0,sonsuz);
	op(v);
	tip[v]=1;
	array<array<int,2>,2>res=seg.query(bas[1],bas[bottom[1]]);
	return min(min(res[0][0],res[0][1]),min(res[1][0],res[1][1]));
}

int dog(int v){
	sil(v);
	seg.update(bas[v],1,sonsuz);
	op(v);
	tip[v]=2;
	array<array<int,2>,2>res=seg.query(bas[1],bas[bottom[1]]);
	return min(min(res[0][0],res[0][1]),min(res[1][0],res[1][1]));
}

int neighbor(int v){
	sil(v);
	seg.update(bas[v],tip[v]-1,-sonsuz);
	op(v);
	tip[v]=0;
	array<array<int,2>,2>res=seg.query(bas[1],bas[bottom[1]]);
	return min(min(res[0][0],res[0][1]),min(res[1][0],res[1][1]));
}

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