Submission #118078

#	Time	Username	Problem	Language	Result	Execution time	Memory
118078		kig9981	Cats or Dogs (JOI18_catdog)	C++17	0 / 100	6 ms	3712 KiB

catdog

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

using namespace std;

const int SZ=1<<17;
vector<int> adj[100000];
int node_cnt, depth[100000], parent[100000], W[100000], num[100000], num_rev[100000], hld[100000], V[100000], ans;
pair<int,int> tree[2*SZ], itree[2*SZ];

void set_tree(int n, int v)
{
	for(itree[n+=SZ].first=v;n>>=1;) itree[n]=max(itree[2*n],itree[2*n+1]);
}

pair<int,int> get_max(int s, int e)
{
	pair<int,int> ret;
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) ret=max(ret,itree[s++]);
		if(~e&1) ret=max(ret,itree[e--]);
	}
	return ret;
}

void add_tree(int s, int e, int v1, int v2)
{
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) {
			tree[s].first+=v1;
			tree[s++].second+=v2;
		}
		if(~e&1) {
			tree[e].first+=v1;
			tree[e--].second+=v2;
		}
	}
}

pair<int,int> get_value(int n)
{
	pair<int,int> ret;
	for(ret=tree[n+=SZ];n>>=1;) {
		ret.first+=tree[n].first;
		ret.second+=tree[n].second;
	}
	return ret;
}

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

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

void initialize(int N, vector<int> A, vector<int> B)
{
	itree[N-1].second=N-1; parent[0]=-1;
	for(int i=0;i<N-1;i++) {
		adj[--A[i]].push_back(--B[i]);
		adj[B[i]].push_back(A[i]);
		itree[i].second=i;
	}
	dfs(0); dfs2(0);
	for(int i=SZ-1;i;i--) itree[i]=max(itree[2*i],itree[2*i+1]);
}

int query(int a)
{
	while(a>=0) {
		auto temp=get_max(num[hld[a]],num[a]);
		if(temp.first) {
			int s=hld[a], e=a;
			while(s<=e) {
				int m=(s+e)>>1;
				temp=get_max(num[m],num[a]);
				if(temp.first) s=m+1;
				else e=m-1;
			}
			return temp.second;
		}
		a=parent[hld[a]];
	}
	return 0;
}

void update(int a, int b, int v1, int v2)
{
	if(b==-1) return;
	while(hld[a]!=hld[b]) {
		add_tree(num[hld[b]],num[b],v1,v2);
		b=parent[hld[b]];
	}
	add_tree(num[a],num[b],v1,v2);
}

int cat(int c)
{
	int idx=num[--c], pidx=query(c);
	auto[v1,v2]=get_value(idx);
	auto[pv1,pv2]=get_value(pidx);
	if(pidx || V[pidx]) {
		if(V[pidx]==1) ans-=pv2;
		else if(V[pidx]==2) ans-=pv1-1;
	}
	else ans+=min(pv1+1-v1,pv2-v2)-min(pv1,pv2);
	V[idx]=1; set_tree(idx,1);
	ans+=v2;
	update(num_rev[pidx],parent[num_rev[idx]],1-v1,-v2);
	return ans;
}

int dog(int c)
{
	int idx=num[--c], pidx=query(c);
	auto[v1,v2]=get_value(idx);
	auto[pv1,pv2]=get_value(pidx);
	if(pidx || V[pidx]) {
		if(V[pidx]==1) ans-=pv2-1;
		else if(V[pidx]==2) ans-=pv1;
	}
	else ans+=min(pv1-v1,pv2+1-v2)-min(pv1,pv2);
	V[idx]=2; set_tree(idx,2);
	ans+=v1;
	update(num_rev[pidx],parent[num_rev[idx]],-v1,1-v2);
	return ans;
}

int neighbor(int c)
{
	int idx=num[--c], pidx=query(parent[c]);
	auto[v1,v2]=get_value(idx);
	auto[pv1,pv2]=get_value(pidx);
	if(pidx || V[pidx]) {
		if(V[pidx]==1) ans-=pv2-v2;
		else if(V[pidx]==2) ans-=pv1-v1;
	}
	else ans+=min(pv1+v1-(V[idx]==1),pv2+v2-(V[idx]==2))-min(pv1,pv2);
	if(V[idx]==1) ans-=v2;
	else if(V[idx]==2) ans-=v1;
	update(num_rev[pidx],parent[num_rev[idx]],v1-(V[idx]==1),v2-(V[idx]==2));
	V[idx]=0; set_tree(idx,0);
	return ans;
}

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