Submission #1143808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143808		raspy	Cats or Dogs (JOI18_catdog)	C++20	100 / 100	121 ms	32584 KiB

catdog

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

using namespace std;

const int64_t inf = 1e15;

struct Node {
	int64_t dp[2][2];
};

struct SegT
{
	vector<Node> seg;
	int64_t n;
	int64_t s;
	SegT() {
	}
	SegT(int64_t _n) {
		n=_n;
		s=1;
		while (s<n)s*=2;
		seg.resize(2*s);
		for (int64_t i=s; i<2*s; i++) {
			seg[i].dp[0][0]=seg[i].dp[1][1]=0;
			seg[i].dp[0][1]=seg[i].dp[1][0]=inf;
		}
		for (int64_t i = s-1; i; i--)
			upd(i);
	}
	void upd(int64_t i) {
		seg[i].dp[0][0]=seg[i].dp[1][1]=inf;
		seg[i].dp[0][1]=seg[i].dp[1][0]=inf;
		for (int64_t a = 0; a < 2; a++)
			for (int64_t b = 0; b < 2; b++)
				for (int64_t c = 0; c < 2; c++)
					for (int64_t d = 0; d < 2; d++)
						seg[i].dp[a][d] = min(seg[i].dp[a][d], seg[i*2].dp[a][b]+
							seg[i*2+1].dp[c][d]+(b!=c));
	}
	void get(int64_t& mc, int64_t& ps) {
		int64_t a = min(seg[1].dp[0][0],seg[1].dp[0][1]);
		int64_t b = min(seg[1].dp[1][0],seg[1].dp[1][1]);
		ps=min(a, b+1);
		mc=min(a+1, b);
	}
	void add(int64_t i, int64_t dm, int64_t dp) {
		i+=s;
		seg[i].dp[0][0]+=dp;
		seg[i].dp[1][1]+=dm;
		while (i>>=1)
			upd(i);
	}
};

vector<int64_t> graf[100005];
int64_t hut[100005];
int64_t par[100005];
int64_t heavy[100005];
int64_t gl[100005];
int64_t skp[100005];
int64_t skpar[100005];
int64_t hsz[100005];
int64_t pos[100005];
int64_t m;
SegT seg[100005];

int64_t dfs(int64_t u)
{
	int64_t sz = 1, mx_sz = 0;
	for (int64_t v:graf[u]) {
		if (v == par[u]) continue;
		par[v]=u;
		gl[v]=gl[u]+1;
		int64_t t_sz = dfs(v);
		if (t_sz > mx_sz)
			mx_sz=t_sz, heavy[u]=v;
		sz+=t_sz;
	}
	return sz;
}

void hld(int64_t u, int64_t id)
{
	skp[u]=id;
	if (hsz[id]==0)
		skpar[id]=par[u];
	pos[u]=hsz[id]++;
	if (heavy[u] != -1)
		hld(heavy[u], id);
	for (int64_t v:graf[u]) {
		if (v==heavy[u] || v == par[u]) continue;
		hld(v, m++);
	}
}

int64_t upd(int64_t v, int64_t dp, int64_t dm) {
	while (v!=-1)
	{
		int64_t t_sk = skp[v];
		int64_t cm, cp;
		seg[t_sk].get(cm, cp);
		seg[t_sk].add(pos[v], dm, dp);
		int64_t nm, np;
		seg[t_sk].get(nm, np);
		dm = nm-cm;
		dp = np-cp;
		v=skpar[t_sk];
	}
	int64_t mc, p;
	seg[0].get(mc, p);
	return min(mc, p);
}

void initialize(int n, vector<int> a, vector<int> b)
{
	memset(heavy, -1, sizeof(heavy));
	for (int64_t i = 0; i < n-1; i++)
	{
		graf[a[i]-1].push_back(b[i]-1);
		graf[b[i]-1].push_back(a[i]-1);
	}
	dfs(0);
	hld(0, m++);
	skpar[0] = -1;
	for (int64_t i = 0; i < m; i++)
		seg[i] = SegT(hsz[i]);
}

int cat(int v)
{
	v--;
	hut[v] = 1;
	return upd(v, 0, inf);
}

int dog(int v)
{
	v--;
	hut[v] = 2;
	return upd(v, inf, 0);
}

int neighbor(int v)
{
	v--;
	int64_t r = 0;
	if (hut[v] == 1)
		r = upd(v, 0, -inf);
	else if (hut[v] == 2)
		r = upd(v, -inf, 0);
	hut[v] = 0;
	return r;
}

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