九校联考Day2 - 3.管理 题解

九校联考Day2 - 3.管理 题解

题意：n 个员工， m 次操作，操作分为以下三种：

九校联考Day2 - 3.管理 题解

题意

$n$ 个员工， $m$ 次操作，操作分为以下三种：

1. 任命一个员工是另一员工的上司（上司关系不构成还），即构成一个森林的。

2. 在一个员工处产生一个新文件，他的所有上司和他会阅读这份文件。

3. 查询之前的一个文件是否被某个人阅读。

数据范围

测试点编号	$n$	$m$	特殊性
$1-4$	$n \le 1000$	$m \le 1000$	/
$5-10$	$n \le 30000$	$m \le 3000$	$1$ 号员工无上司，若员工$ i>=2 $ 有直接上司，则一定是员工 $i - 1$
$11-16$	$n \le 150000$	$m \le 300000$	所有操作 1 在操作 2 和 3 前
$17 - 20$	$n \le 150000$	$m \le 300000$	/

5 - 10

因为一个员工 $i$ 的上司一定在 $i$ 前面，因此只要员工 $j$ （$j < i$）满足此时 $i$ 与 $j$ 联通，那 $j$ 一定是 $i$ 的上司，直接并查集处理即可。

11 - 16

这个特殊性使得我们可以提前处理这个森林，用 $\texttt{LCA}$ 或者 $\texttt{dfs}$ 序等方法判断一个员工是否是另一个员工的祖先即可。

满分做法

从上面的部分分做法获得启示，我们考虑在当前两个员工 $x$，$y$ 联通时，因为是树，所以此时这两个员工的相对位置已经确定了，不管再怎么进行操作 1，$x$ 如果是 $y$ 的祖先那他肯定还是，不是也不可能让它变成 $y$ 的祖先。因此，我们要判断在一个时刻 $x$ 是否是 $y$ 的祖先，相当于判断在当前时刻 $x$，$y$ 是否联通，在最后形成的森林中 $x$ 是否是 $y$ 的祖先。因此，我们得到以下的做法：

• 输入所有操作，执行操作 1，处理森林；
• 将所有操作 3 标记在相应的操作 2 上；
• 按时间遍历操作 1 和 2，对于操作 1 执行并查集合并，对于操作 2 遍历所含的 3 ，判断是否联通，以及在预处理的森林中是否是祖先关系。

CODE

#include <bits/stdc++.h>
using namespace std;
#define N 1500010
#define pb push_back
typedef int Ary[N];

int n, m, fl = 0, cnt = 0, dfn = 0, tot = 0;
Ary File, hd, L, R, fa, res;
vector<int> e[N];

struct qes {
	int op, x, y;
	qes(int op = 0, int x = 0, int y = 0) : op(op), x(x), y(y) {}
}q[N]; vector<qes> Ask[N];

int getF(int x) {
	return fa[x] == x ? x : fa[x] = getF(fa[x]);
}

void dfs(int x, int fa) {
	L[x] = ++ dfn;
	for (auto i : e[x]) dfs(i, x);
	R[x] = dfn;
}

int main() {
	freopen("manage.in", "r", stdin);
	freopen("manage.out", "w", stdout);

	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i ++) {
		int op, x, y; scanf("%d%d", &op, &x);
		if (op != 2) scanf("%d", &y);
		else q[++ cnt] = qes(op, x);
		if (op == 1) e[y].pb(x), fa[x] = 1, q[++ cnt] = qes(op, x, y);
		if (op == 3) Ask[y].pb(qes(i, x));
	}

	for (int i = 1; i <= n; i ++) if (!fa[i]) dfs(i, 0);

	for (int i = 1; i <= n; i ++) fa[i] = i;

	memset(res, -1, sizeof res);
	for (int i = 1, t = 0; i <= cnt; i ++) {
		if (q[i].op == 1) fa[getF(q[i].x)] = getF(q[i].y);
		else for (auto j : Ask[++ t]) {
			res[j.op] = 
				(getF(q[i].x) == getF(j.x) &&
				L[j.x] <= L[q[i].x] && L[q[i].x] <= R[j.x]);
		}
	}

	for (int i = 1; i <= m; i ++) {
		~res[i] ? (res[i] ? puts("YES") : puts("NO")) : i = i;
	}
	return 0;
}