【51Nod 1815】【算法马拉松 23】调查任务

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1815

tarjan缩点后在DAG上递推即可。

每个点维护所有根到它的路径上的值的最大值，严格次大值，最大的“根到这个点的一条路径中的严格次大值”（也就是答案）。

注意所有根到它的路径上的值的严格次大值不是答案。

时间复杂度\(O(n)\)。

#include<cstdio>

#include<bitset>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 400003;

const int M = 2000003;

struct node {int nxt, to;} E[M], E2[M], E3[M];

int cnt = 0, cnt3 = 0, point[N], point2[N], cur[N], du[N], point3[N];

void ins(int u, int v) {E[++cnt] = (node) {point[u], v}; point[u] = cnt;}

void ins2(int u, int v) {

	E2[++cnt] = (node) {point2[u], v}; point2[u] = cnt;

	E3[++cnt3] = (node) {point3[v], u}; point3[v] = cnt3;

}

bitset <N> inst;

int dfn[N], low[N], tot = 0, a[N], sta[N], statop, st[N], top, bel[N], n, m, q, s, fa[N];

void tarjan(int x) {

	st[top = 1] = x; statop = 0;

	while (top) {

		int u = st[top];

		if (!dfn[u]) {

			dfn[u] = low[u] = ++cnt;

			sta[++statop] = u;

			inst[u] = 1;

		}

		if (cur[u]) {

			int v = E[cur[u]].to;

			if (!dfn[v]) fa[st[++top] = v] = u;

			else if (inst[v]) low[u] = min(low[u], dfn[v]);

			cur[u] = E[cur[u]].nxt;

		} else {

			low[fa[u]] = min(low[fa[u]], low[u]);

			if (dfn[u] == low[u]) {

				++tot;

				while (sta[statop] != u) {

					inst[sta[statop]] = 0;

					bel[sta[statop]] = tot;

					--statop;

				}

				inst[u] = 0;

				bel[u] = tot;

				--statop;

			}

			--top;

		}

	}

}

bitset <N> vis;

int max1[N], max2[N], max3[N], qu[N], A[4];

void BFS() {

	int p = 0, q = 1;

	vis[qu[1] = bel[s]] = 1;

	while (p != q) {

		int u = qu[++p];

		for (int i = point2[u]; i; i = E2[i].nxt) {

			int v = E2[i].to;

			++du[v];

			if (!vis[v]) {

				vis[v] = 1;

				qu[++q] = v;

			}

		}

	}

	p = 0; q = 1; qu[1] = bel[s];

	while (p != q) {

		int u = qu[++p];

		for (int i = point3[u]; i; i = E3[i].nxt) {

			int v = E3[i].to;

			if (vis[v]) {

				if (max1[v] > max1[u]) {max3[u] = max1[u]; max1[u] = max1[v];}

				else if (max1[v] < max1[u] && max1[v] > max3[u]) max3[u] = max1[v];

				if (max3[v] > max1[u]) {max3[u] = max1[u]; max1[u] = max3[v];}

				else if (max3[v] < max1[u] && max3[v] > max3[u]) max3[u] = max3[v];

			}

		}

		for (int i = point2[u]; i; i = E2[i].nxt) {

			int v = E2[i].to;

			max2[v] = max(max2[v], max2[u]);

			if (max1[u] != max1[v]) max2[v] = max(max2[v], min(max1[u], max1[v]));

			else max2[v] = max(max2[v], max(max3[u], max3[v]));

			if (--du[v] == 0) qu[++q] = v;

		}

	}

}

int main() {

	scanf("%d%d%d%d", &n, &m, &q, &s);

	for (int i = 1; i <= n; ++i)

		scanf("%d", a + i);

	int u, v;

	for (int i = 1; i <= m; ++i) {

		scanf("%d%d", &u, &v);

		ins(u, v);

	}

	cnt = 0;

	for (int i = 1; i <= n; ++i)

		cur[i] = point[i], max1[i] = max2[i] = -1;

	for (int i = 1; i <= n; ++i)

		if (!dfn[i]) tarjan(i);

	cnt = 0;

	for (int i = 1; i <= n; ++i)

		for (int j = point[i]; j; j = E[j].nxt)

			if (bel[i] != bel[E[j].to])

				ins2(bel[i], bel[E[j].to]);

	for (int i = 1; i <= n; ++i) {

		int t = bel[i];

		if (a[i] > max1[t]) max2[t] = max1[t], max1[t] = a[i];

		else if (a[i] < max1[t] && a[i] > max2[t]) max2[t] = a[i];

	}

	for (int i = 1; i <= tot; ++i) max3[i] = max2[i];

	BFS();

	for (int i = 1; i <= q; ++i) {

		scanf("%d", &u);

		if (!vis[bel[u]]) printf("-1 ");

		else if (max2[bel[u]] == -1) printf("0 ");

		else printf("%d ", max2[bel[u]]);

	}

	return 0;

}