Description

link

题意概述：现在有一条长度为 \(n\) 的链，有些边是有限制的

限制为能到某个点，才能经过这条边

给定多组询问，看给定的起始点 \(S\) 是否可以到达 \(T\)

\(n \leq 10^6\)

Solution

\[Begin
\]

还是比较好看出来这个题要预处理每一个点的可达区间 \([\space l_i,r_i \space ]\)

先缩点，就是在没有钥匙的情况下每个点的左右可达

考虑我们怎么在比较短的时间内完成这个事情：

一个很愚蠢但是有用的结论：我们达到了一个点 \(i\) 就可以达到区间 \([\space l_i,r_i \space ]\)

这个玩意好像很单调，然后就\(dfs\)就可以完成预处理了……

我其实感觉这玩意有点像什么单调数据结构，或者就是个记忆化搜索……

\[QED
\]

Code

#include<bits/stdc++.h>

using namespace std;

#define int long long

namespace yspm{

	inline int read()

	{

		int res=0,f=1; char k;

		while(!isdigit(k=getchar())) if(k=='-') f=-1;

		while(isdigit(k)) res=res*10+k-'0',k=getchar();

		return res*f;

	}

	const int N=1e6+10;

	int scc[N],a[N],l[N],r[N],vis[N],n,m,T;

	inline void dfs(int x)

	{

		if(vis[x]) return ;

		int tl=x,tr=x,fl=0;

		while(!fl)

		{

			if(tl<=a[tl-1]&&a[tl-1]<=tr) fl=1,dfs(tl-1),tl=l[tl-1];

			if(tl<=a[tr]&&a[tr]<=tr) fl=1,dfs(tr+1),tr=r[tr+1];

			fl=!fl;

		}l[x]=tl,r[x]=tr,vis[x]=1; return ;

	}

	signed main()

	{

		n=read(); m=read()+1; T=read(); scc[1]=1;

		for(int i=1;i<=m-1;++i) a[read()]=read();

		for(int i=1;i<=n;++i) scc[i+1]=scc[i]+(bool) a[i];

		for(int i=1;i<=n;++i) if(a[i]) a[scc[i]]=scc[a[i]];

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

		while(T--)

		{

			int x=scc[read()],y=scc[read()];

			puts(l[x]<=y&&y<=r[x]?"YES":"NO");

		} return 0;

	}

}

signed main(){return yspm::main();}

巴特西

HNOI2018/AHOI2018 游戏

Description

Solution

Code

最新文章

热门文章