Submission #781857

#	Time	Username	Problem	Language	Result	Execution time	Memory
781857		kshitij_sodani	Cats or Dogs (JOI18_catdog)	C++14	100 / 100	592 ms	109020 KiB

catdog

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
//#define endl '\n'


#include "catdog.h"

llo x;
vector<llo> adj[100001];
llo dp[100001][2];
llo it[100001];
llo par[100001];
llo ss[100001];
llo st[100001];
llo par3[100001];
llo n;
vector<vector<vector<llo>>> tree[100001];
vector<llo> pre[100001];

void dfs(llo no,llo par2=-1){
	ss[no]=1;
	par[no]=par2;
	vector<pair<llo,llo>> tt;
	for(auto j:adj[no]){
		if(j!=par2){
			dfs(j,no);
			tt.pb({ss[j],j});
			ss[no]+=ss[j];
		}
	}
	sort(tt.begin(),tt.end());
	adj[no].clear();
	while(tt.size()){
		adj[no].pb(tt.back().b);
		tt.pop_back();
	}
}
llo co=0;

void dfs2(llo no,llo par2=-1){
	par3[no]=no;
	st[no]=co;
	co++;
	if(par2!=-1){
		if(st[no]==st[par2]+1){
			par3[no]=par3[par2];
		}
	}
//	ind[no]=pre[par3[no]].size();
	pre[par3[no]].pb(no);
	vector<llo> kk;
	kk.pb(0);
	kk.pb(0);
	vector<vector<llo>> ll;
	ll.pb(kk);
	ll.pb(kk);
	for(llo i=0;i<4;i++){
		tree[par3[no]].pb(ll);
	}
	for(auto j:adj[no]){
		if(j!=par2){
			dfs2(j,no);
		}
	}
}
void build(llo ind,llo no,llo l,llo r){
	if(l==r){
		tree[ind][no][0][0]=0;
		tree[ind][no][1][1]=0;
		tree[ind][no][1][0]=1e6;
		tree[ind][no][0][1]=1e6;
	}
	else{
		llo mid=(l+r)/2;
		build(ind,no*2+1,l,mid);
		build(ind,no*2+2,mid+1,r);
		tree[ind][no][0][0]=0;
		tree[ind][no][1][1]=0;
		tree[ind][no][1][0]=1e6;
		tree[ind][no][0][1]=1e6;		/*for(llo i=0;i<2;i++){
			for(llo j=0;j<2;j++){
				for(llo l=0;l<2;l++){
					for(llo k=0;k<2;k++){
						llo x=1;
						if(j==l){
							x=0;
						}
						tree[ind][no][i][k]=min(tree[ind][no][i][k],tree[ind][no*2+1][i][j]+tree[ind][no*2+2][l][k]+x);
					}
				}
			}
		}*/

	}
}
void update(llo ind,llo no,llo l,llo r,llo i,llo j){
	if(l==r){
		tree[ind][no][0][0]=dp[j][0];
		tree[ind][no][1][1]=dp[j][1];
		if(it[j]==2){
			//cout<<22<<endl;
			tree[ind][no][0][0]=1e6;
		}
		if(it[j]==1){

			tree[ind][no][1][1]=1e6;
		}
	//	cout<<j<<","<<tree[ind][no][0][0]<<","<<tree[ind][no][1][1]<<endl;
		tree[ind][no][1][0]=1e6;
		tree[ind][no][0][1]=1e6;
	}
	else{
		llo mid=(l+r)/2;
		if(i<=mid){
			update(ind,no*2+1,l,mid,i,j);
		}
		else{
			update(ind,no*2+2,mid+1,r,i,j);
		}
		tree[ind][no][0][0]=1e6;
		tree[ind][no][1][1]=1e6;
		tree[ind][no][1][0]=1e6;
		tree[ind][no][0][1]=1e6;
		for(llo ii=0;ii<2;ii++){
			for(llo jj=0;jj<2;jj++){
				for(llo l=0;l<2;l++){
					for(llo k=0;k<2;k++){
						llo x=0;
						if(jj!=l){
							x++;
						}
						/*if(j==6 and no==0 and  tree[ind][no*2+1][ii][jj]+tree[ind][no*2+2][l][k]+x==0){
							cout<<1111<<endl;
							cout<<ii<<":"<<jj<<":"<<l<<":"<<k<<endl;
						}*/
						tree[ind][no][ii][k]=min(tree[ind][no][ii][k],tree[ind][no*2+1][ii][jj]+tree[ind][no*2+2][l][k]+x);
					}
				}
			}
		}
	/*	if(no==0){
			cout<<tree[ind][no*2+1][0][0]<<"?"<<tree[ind][no*2+2][1][1]<<endl;
		}*/

	}
	/*cout<<no<<":"<<l<<":"<<r<<endl;
	for(int ii=0;ii<2;ii++){
		for(int jj=0;jj<2;jj++){
			cout<<tree[ind][no][ii][jj]<<"<";
		}
		cout<<endl;
	}*/
}
void initialize(int nn, std::vector<int> aa, std::vector<int> bb) {
	n=nn;
	for(llo i=0;i<n-1;i++){
		adj[aa[i]-1].pb(bb[i]-1);
		adj[bb[i]-1].pb(aa[i]-1);
	}
	dfs(0);
	dfs2(0);
	for(llo i=0;i<n;i++){
		if(pre[i].size()){
			build(i,0,0,pre[i].size()-1);
		}
	}
	for(llo i=0;i<n;i++){
		it[i]=0;
		dp[i][0]=0;
		dp[i][1]=0;
	}
}
void apply(llo i){
	//<llo> xx;
 	llo cur=i;
 	while(true){
 		cur=par3[cur];
 		if(cur==0){
 			break;
 		}
 		dp[par[cur]][0]-=min(min(tree[cur][0][0][0],tree[cur][0][0][1]),min(tree[cur][0][1][0],tree[cur][0][1][1])+1);
 		dp[par[cur]][1]-=min(min(tree[cur][0][0][0],tree[cur][0][0][1])+1,min(tree[cur][0][1][0],tree[cur][0][1][1]));
 		cur=par[cur];
 	}
 	update(par3[i],0,0,pre[par3[i]].size()-1,st[i]-st[par3[i]],i);
 //	cout<<i<<"::"<<par3[i]<<endl;
 //	cout<<st[i]-st[par3[i]]<<endl;
 	cur=i;
 	while(true){
 		cur=par3[cur];
 		if(cur==0){
 			break;
 		}
 		dp[par[cur]][0]+=min(min(tree[cur][0][0][0],tree[cur][0][0][1]),min(tree[cur][0][1][0],tree[cur][0][1][1])+1);
 		dp[par[cur]][1]+=min(min(tree[cur][0][0][0],tree[cur][0][0][1])+1,min(tree[cur][0][1][0],tree[cur][0][1][1]));
 		cur=par[cur];
 	//	cout<<11<<endl;
 		update(par3[cur],0,0,pre[par3[cur]].size()-1,st[cur]-st[par3[cur]],cur);
 	}
}
int cat(int i) {
	i--;
	it[i]=1;
	apply(i);
 	//dp[i][1]=1e6;
 //	dfs(0);
 	llo ans=1e6;
 	for(llo i=0;i<2;i++){
 		for(llo j=0;j<2;j++){
 			ans=min(ans,tree[0][0][i][j]);
 		}
 	}
 /*	for(llo i=0;i<n;i++){
 		cout<<dp[i][0]<<","<<dp[i][1]<<endl;
 	}*/
 //	cout<<ans<<endl;
	return ans;
}

int dog(int i) {
	i--;
	it[i]=2;
	apply(i);
 	llo ans=1e6;
 //	cout<<dp[0][0]<<":"<<dp[0][1]<<endl;
 //	cout<<tree[0][0][0][1]<<":::"<<endl;
  	//	cout<<par3[i]<<"::"<<endl;
 	for(llo i=0;i<2;i++){
 		for(llo j=0;j<2;j++){
 			ans=min(ans,tree[0][0][i][j]);
 			//<<tree[0][0][i][j]<<",,";
 		}
 		//cout<<endl;
 	}

 /*	for(llo i=0;i<n;i++){
 		cout<<dp[i][0]<<","<<dp[i][1]<<endl;
 	}*/
 	//cout<<ans<<endl;

	return ans;
}

int neighbor(int i) {
	i--;
	it[i]=0;
	apply(i);
 	llo ans=1e6;
 	for(llo i=0;i<2;i++){
 		for(llo j=0;j<2;j++){
 			ans=min(ans,tree[0][0][i][j]);
 		}
 	}

 	/*for(llo i=0;i<n;i++){
 		cout<<dp[i][0]<<","<<dp[i][1]<<endl;
 	}*/
 	//cout<<ans<<endl;
	return ans;
}

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