题解 【P6378 [PA2010] Riddle】

非常腻害（？）的一个科技，前缀优化建图。

首先看到”每条边至少有一个端点是关键点”珂以想到 2-SAT，对于每个点建立两个点 $x_1,x_2$ 分别表示 $x$ 不是关键点和是关键点。

对于每条原图中的边 $x\rightarrow y$，在 2-SAT 的图中连 $x_1\rightarrow y_2,y1\rightarrow x_2$ 这两条边。

但是每个部分只能有一个关键点，为了满足这个需求我们需要对于每个在这个部分 $i$ 里的 $x$ 点，从 $x_2$ 向 $i$ 部分其它所有点 $y$ 的 $y_1$ 连边。你当然可以线段树优化建图，但是太慢了还很可能会被卡（雾

所以前缀优化建图到底是什么东西？我们定义前缀为 $x$ 节点所在的部分，按照题目中的输入顺序中，在 $x$ 前面输入的部分（包含 $x$ 本身）。比如对于样例，$4$ 的前缀就是 $3,4$。

对于每个点再建立两个点 $x_3,x_4$ 分别表示前缀没有关键点和有关键点，那么如果 $x$ 本身就是关键点，前缀肯定有关键点，所以连一条 $x_2\rightarrow x_4$ 的边。

同理，如果前缀都没有关键点，$x$ 本身肯定也不是关键点，所以从 $x_3$ 向 $x_1$ 连边。

接下来考虑 $x$ 以及输入顺序中在 $i$ 前一个输入的点 $y$（$x$ 和 $y$ 是一个部分的点）。

• 如果 $y$ 的前缀有关键点，则 $x$ 前缀也有关键点，连边 $y_4\rightarrow x_4$。
• 如果 $x$ 前缀没有关键点，则 $y$ 前缀可定没有关键点，连边 $x_3\rightarrow y_3$。
• 如果 $y$ 前缀已经有了关键点，那么 $x$ 就不能是关键点了，连边 $y_4\rightarrow x_1$。
• 如果 $x$ 是关键点，$y$ 前缀肯定不能有关键点，连边 $x_2\rightarrow y_3$。

补充一下，其实在上面的连边过程中有些边我们没有连，比如 $x$ 是关键点，$y$ 肯定不是关键点。但如果 $x$ 是关键点，$y$ 的前缀都没有关键点，$y$ 怎么可能是关键点？图中也有 $x_3\rightarrow y_3\rightarrow y_1$ 的边。

虽然点数有 $4$ 的常数，边数有 $8$ 的常数，但随便怎么样还是把线段树这些常数和复杂度都上天的东西吊着打（

/*
x_1 编号是 x
x_2 编号是 x+n 
x_3 编号是 x+3*n
x_4 编号是 x+2*n 
*/
#include <cstdio>
#include <cstring>
#define gc (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 65536, stdin), p1 == p2) ? EOF : *p1 ++)
const int N = 8000005, M = 10000005;
inline int min(const int x, const int y) {return x < y ? x : y;}

char buf[65536], *p1, *p2;
inline int read() {
	char ch;
	int x = 0;
	while ((ch = gc) < 48);
	do x = x * 10 + ch - 48; while ((ch = gc) >= 48);
	return x;
}

int n, m, k;
struct TwoSAT {
	struct Edge {
		int to, nxt;
	} e[M];
	int head[N], s[N], dfn[N], low[N], col[N], tot, top, cnt, scc;
	bool Instack[N];
	inline void AddEdge(const int u, const int v) {
		e[++ tot].to = v, e[tot].nxt = head[u], head[u] = tot;
	}
	void Tarjan(int u) {
		dfn[u] = low[u] = ++ cnt, s[++ top] = u, Instack[u] = true;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if (!dfn[v]) Tarjan(v), low[u] = min(low[u], low[v]);
			else if (Instack[v]) low[u] = min(low[u], dfn[v]);
		}
		if (dfn[u] == low[u]) {
			++ scc;
			do
				col[s[top]] = scc, Instack[s[top]] = false;
			while (s[top --] != u);
		}
	}
	bool solve() {
		for (int i = 1; i <= 4 * n; ++ i)
			if (!dfn[i]) Tarjan(i);
		for (int i = 1; i <= n; ++ i)
			if (col[i] == col[i + n] || col[i + 2 * n] == col[i + 3 * n])
				return false;
		return true;
	}
} solver;

int main() {
	n = read(), m = read(), k = read();
	for (int i = 1; i <= m; ++ i) {
		int u = read(), v = read();
		solver.AddEdge(u, v + n);
		solver.AddEdge(v, u + n);
	}
	for (int i = 1; i <= n; ++ i) {
		solver.AddEdge(i + n, i + 2 * n);
		solver.AddEdge(i + 3 * n, i);
	}
	for (int i = 1; i <= k; ++ i) {
		int T, pre, x;
		T = read(), pre = read();
		while (-- T) {
			x = read();
			solver.AddEdge(pre + 2 * n, x + 2 * n);
			solver.AddEdge(x + 3 * n, pre + 3 * n);
			solver.AddEdge(pre + 2 * n, x);
			solver.AddEdge(x + n, pre + 3 * n);
			pre = x;
		}
	}
	puts(solver.solve() ? "TAK" : "NIE");
	return 0;
}