[HNOI2018]游戏[拓扑排序]

时间：2021-12-20 15:20:35

题意

题目链接

分析

  • 先将没有锁的房间缩点，首先有一个 \(O(n^2)\) 的想法：从每个点出发，每次检查能否向两边扩张。
  • 容易发现门和门之间如果有锁，必然只有一方能够开锁(只有一把钥匙)，并且能够开一扇门的位置一定是一个区间 \([l,r]\)。假设门 \(p<l\) ，则区间内的所有门都为 \(\leftarrow\) 。如果扩展顺序为 \(l\) 到 \(r\) 就可以保证对于开 \(p​\) 门这个操作只被进行一次，而后面的位置可以继承这个可行区间。
  • 所以如果对于门 \(a\)，如果钥匙在 \(a\) 左边，就连边 \(a+1 \rightarrow a\) ，反之同理。按照拓扑序扩展就可以保证扩展次数至多为 \(m\) 次。
  • 时间复杂度 \(O(n+m)\) 。

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define go(u) for(int i = head[u], v = e[i].to; i; i=e[i].lst, v=e[i].to)

#define rep(i, a, b) for(int i = a; i <= b; ++i)

#define pb push_back

#define re(x) memset(x, 0, sizeof x)

inline int gi() {

    int x = 0,f = 1;

    char ch = getchar();

    while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar();}

    while(isdigit(ch)) { x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}

    return x * f;

}

template <typename T> inline bool Max(T &a, T b){return a < b ? a = b, 1 : 0;}

template <typename T> inline bool Min(T &a, T b){return a > b ? a = b, 1 : 0;}

const int N = 1e6 + 7;

int n, m, p, ndc;

int x[N], y[N], pos[N], du[N], id[N], L[N], R[N];

bool lck[N];

vector<int>G[N];

queue<int>Q;

void solve() {

	rep(i, 1, ndc) L[i] = R[i] = i;

	rep(i, 1, ndc) if(!du[i]) Q.push(i);

	while(!Q.empty()) {

		int u = Q.front();Q.pop();

		while(1) {

			bool fg = 0;

			if(u > 1 && L[u] <= pos[L[u] - 1] && pos[L[u] - 1] <= R[u]) fg = 1, L[u] = L[L[u] - 1];

			if(u < ndc && L[u] <= pos[R[u]] && pos[R[u]] <= R[u]) fg = 1, R[u] = R[R[u] + 1];

			if(!fg) break;

		}

		for(auto v:G[u]) {

			if(--du[v] == 0) Q.push(v);

		}

	}

}

int main() {

	n = gi(), m = gi(), p = gi();

	rep(i, 1, m) {

		x[i] = gi(), y[i] = gi();

		lck[x[i]] = 1;

	}

	id[1] = ++ndc;

	rep(i, 2, n) {

		if(lck[i - 1]) id[i] = ++ndc;

		else id[i] = id[i - 1];

	}

	rep(i, 1, m) pos[id[x[i]]] = id[y[i]];

	rep(i, 1, m) {

		x[i] = id[x[i]], y[i] = id[y[i]];

		if(y[i] <= x[i]) G[x[i] + 1].pb(x[i]), ++du[x[i]];

		if(y[i] > x[i]) G[x[i]].pb(x[i] + 1), ++du[x[i] + 1];

	}

	solve();

	while(p--) {

		int s = id[gi()], t = id[gi()];

		if(L[s] <= t && t <= R[s]) puts("YES");

		else puts("NO");

	}

	return 0;

}

相关文章