제출 #978180

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
978180		vjudge1	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	405 ms	28244 KiB

catdog

// #include "catdog.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 100000;
int n, m, u, v, add[2], sub[2], color[100005], f[100005][2], _g[100005][2];
int cnt, fa[100005], siz[100005], dep[100005], son[100005], dfn[100005], top[100005], rnk[100005], bot[100005];
vector<int> e[100005];
struct matrix {
	int v[2][2];
	matrix(int val = inf) {
		v[0][0] = val, v[0][1] = inf;
		v[1][0] = inf, v[1][1] = val;
	}
	matrix operator = (const matrix& _) {
		v[0][0] = _.v[0][0], v[0][1] = _.v[0][1];
		v[1][0] = _.v[1][0], v[1][1] = _.v[1][1];
		return *this;
	}
	matrix operator * (const matrix& _) const {
		matrix ret;
		ret.v[0][0] = min(v[0][0] + _.v[0][0], v[0][1] + _.v[1][0]);
		ret.v[0][1] = min(v[0][0] + _.v[0][1], v[0][1] + _.v[1][1]);
		ret.v[1][0] = min(v[1][0] + _.v[0][0], v[1][1] + _.v[1][0]);
		ret.v[1][1] = min(v[1][0] + _.v[0][1], v[1][1] + _.v[1][1]);
		return ret;//循环展开后的广义矩阵乘法
	}
} ans, before, after, g[100005];
struct Segment_Tree {//线段树维护转移矩阵
	matrix val[400005];
	int pos, L, R, l[400005], r[400005];
	#define lc (k << 1)
	#define rc ((k << 1) | 1)
	#define mid ((l[k] + r[k]) >> 1)
	void push_up(int k) {
		val[k] = val[lc] * val[rc];
	}
	void build(int k) {
		if(l[k] == r[k]) {
			val[k] = g[rnk[l[k]]];
			return;
		}
		l[lc] = l[k], r[lc] = mid, l[rc] = mid + 1, r[rc] = r[k];
		build(lc), build(rc);
		push_up(k);
	}
	void change(int k) {
		if(l[k] == r[k]) {
			val[k] = g[rnk[pos]];
			return;
		}
		if(pos <= mid) change(lc);
		else change(rc);
		push_up(k);
	}
	matrix ask(int k) {
		if(L <= l[k] && r[k] <= R) return val[k];
		matrix ret(0);
		if(L <= mid) ret = ret * ask(lc);
		if(R > mid) ret = ret * ask(rc);
		return ret;
	}
	void Change(int Pos) {
		pos = Pos;
		return change(1);
	}
	matrix Ask(int l, int r) {
		L = l, R = r;
		return ask(1);
	}
} tree;
//树链剖分
void dfs1(int now) {
	siz[now] = 1, dep[now] = dep[fa[now]] + 1;
	for(const auto& i : e[now]) {
		if(i != fa[now]) {
			fa[i] = now;
			dfs1(i);
			siz[now] += siz[i];
			if(siz[i] > siz[son[now]]) son[now] = i;
		}
	}
}
void dfs2(int now) {
	++cnt; dfn[now] = cnt, rnk[cnt] = now;
	if(now == son[fa[now]]) top[now] = top[fa[now]];
	else top[now] = now;
	if(son[now]) {
		dfs2(son[now]);
		bot[now] = bot[son[now]];
		f[now][0] += min(f[son[now]][0], f[son[now]][1] + 1);
		f[now][1] += min(f[son[now]][0] + 1, f[son[now]][1]);
	}
	else bot[now] = now;
	for(const auto& i : e[now]) {
		if(i != fa[now] && i != son[now]) {
			dfs2(i);
			f[now][0] += min(f[i][0], f[i][1] + 1);
			f[now][1] += min(f[i][0] + 1, f[i][1]);
			_g[now][0] += min(f[i][0], f[i][1] + 1);
			_g[now][1] += min(f[i][0] + 1, f[i][1]);
		}
	}
	g[now].v[0][0] = _g[now][0], g[now].v[0][1] = _g[now][0] + 1;
	g[now].v[1][0] = _g[now][1] + 1, g[now].v[1][1] = _g[now][1];
}
//修改转移矩阵
void change(int now, int val) {
	g[now].v[0][0] = _g[now][0], g[now].v[0][1] = _g[now][0] + 1;
	g[now].v[1][0] = _g[now][1] + 1, g[now].v[1][1] = _g[now][1];
	color[now] = val;
	if(color[now]) g[now].v[color[now] - 1][0] = g[now].v[color[now] - 1][1] = inf;//把不可能出现的一行设为inf
	while(now) {
		before = tree.Ask(dfn[top[now]], dfn[bot[now]]);
		tree.Change(dfn[now]);
		after = tree.Ask(dfn[top[now]], dfn[bot[now]]);
		now = fa[top[now]];
		add[0] = min(after.v[0][0], after.v[0][1]), sub[0] = min(before.v[0][0], before.v[0][1]);
		add[1] = min(after.v[1][0], after.v[1][1]), sub[1] = min(before.v[1][0], before.v[1][1]);
		_g[now][0] += min(add[0], add[1] + 1) - min(sub[0], sub[1] + 1), _g[now][1] += min(add[0] + 1, add[1]) - min(sub[0] + 1, sub[1]);
		g[now].v[0][0] = _g[now][0], g[now].v[0][1] = _g[now][0] + 1;
		g[now].v[1][0] = _g[now][1] + 1, g[now].v[1][1] = _g[now][1];
		if(color[now]) g[now].v[color[now] - 1][0] = g[now].v[color[now] - 1][1] = inf;//不可能出现的状态
	}
}
//下面就是交互了
void initialize(int N, std::vector<int> A, std::vector<int> B) {
	n = N;
	for(int i = 2; i <= n; ++i) {
		u = A[i - 2], v = B[i - 2];
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs1(1);
	dfs2(1);
	tree.l[1] = 1, tree.r[1] = n;
	tree.build(1);
}
int cat(int v) {
	change(v, 1);
	ans = tree.Ask(dfn[top[1]], dfn[bot[1]]);
	return min(min(ans.v[0][0], ans.v[0][1]), min(ans.v[1][0], ans.v[1][1]));
}
int dog(int v) {
	change(v, 2);
	ans = tree.Ask(dfn[top[1]], dfn[bot[1]]);
	return min(min(ans.v[0][0], ans.v[0][1]), min(ans.v[1][0], ans.v[1][1]));
}
int neighbor(int v) {
	change(v, 0);
	ans = tree.Ask(dfn[top[1]], dfn[bot[1]]);
	return min(min(ans.v[0][0], ans.v[0][1]), min(ans.v[1][0], ans.v[1][1]));
}

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