Submission #1246797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246797		PlayVoltz	Cats or Dogs (JOI18_catdog)	C++20	100 / 100	139 ms	31048 KiB

catdog

#include "catdog.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

struct node{
	int s, e, m, val[2][2];
	node *l, *r;
	node(int S, int E){
		s=S, e=E, m=(s+e)/2;
		val[0][0]=val[1][1]=0;
		val[0][1]=val[1][0]=INT_MAX/2;
		if (s!=e){
			val[0][1]=val[1][0]=1;
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void up(int i, int a, int b){
		if (s==e){
			val[0][0]+=a;
			val[1][1]+=b;
			return;
		}
		if (i<=m)l->up(i, a, b);
		else r->up(i, a, b);
		val[0][0]=val[0][1]=val[1][0]=val[1][1]=INT_MAX/2;
		for (int i=0; i<2; ++i)for (int j=0; j<2; ++j)for (int k=0; k<2; ++k)for (int p=0; p<2; ++p)val[i][j]=min(val[i][j], l->val[i][k]+r->val[p][j]+(p^k));
	}
	pii query(){
		return mp(min(min(val[0][0], val[0][1]), min(val[1][1], val[1][0])+1), min(min(val[0][0], val[0][1])+1, min(val[1][1], val[1][0])));
	}
	
	
}*st[100005];

int n, ccounter=0;
vector<int> par, heavy, head, chain, id, counter, vect;
vector<vector<int> > graph;

int dfs(int node, int p){
	par[node]=p;
	int sz=1, mx=0;
	for (auto num:graph[node])if (num!=p){
		int temp=dfs(num, node);
		sz+=temp;
		if (temp>mx)mx=temp, heavy[node]=num;
	}
	return sz;
}

void dfs2(int node, int h){
	head[node]=h;
	chain[node]=chain[h];
	id[node]=counter[chain[node]]++;
	if (heavy[node])dfs2(heavy[node], h);
	for (auto num:graph[node])if (num!=par[node]&&num!=heavy[node])chain[num]=++ccounter, dfs2(num, num);
}

int update(int node, int a, int b){
	pii res, temp;
	for (;node!=-1;node=par[head[node]]){
		temp=st[chain[node]]->query();
		st[chain[node]]->up(id[node], a, b);
		res=st[chain[node]]->query();
		a=res.fi-temp.fi;
		b=res.se-temp.se;
	}
	return min(res.fi, res.se);
}

void initialize(int N, vector<int> a, vector<int> b){
	n=N;
	vect.resize(n+1, 0);
	id.resize(n+1);
	counter.resize(n+1, 1);
	head.resize(n+1, 1);
	chain.resize(n+1, 0);
	par.resize(n+1);
	heavy.resize(n+1, 0);
	graph.resize(n+1);
	for (int i=0; i<n-1; ++i){
		graph[a[i]].pb(b[i]);
		graph[b[i]].pb(a[i]);
	}
	dfs(1, -1);
	dfs2(1, 1);
	for (int i=0; i<=ccounter; ++i)st[i] = new node(1, counter[i]-1);
}

int cat(int a){
	vect[a]=1;
	return update(a, 0, n);
}

int dog(int a){
	vect[a]=2;
	return update(a, n, 0);
}

int neighbor(int a){
	if (vect[a]==1){
		vect[a]=0;
		return update(a, 0, -n);
	}
	vect[a]=0;
	return update(a, -n, 0);
}

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