比赛 20160909 评测结果 AAAAAAA
题目名称 基本的图问题 最终得分 100
用户昵称 Ostmbh 运行时间 1.515 s
代码语言 C++ 内存使用 13.85 MiB
提交时间 2016-09-09 21:57:47
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <stack>
using namespace std;
const int MAX=100000+10;
const int INF=0x7fffffff;
vector<int>A[MAX];
stack<int>s;
int dfn[MAX]={0};
int low[MAX];
int maxx[MAX][21];
int minn[MAX][21];
int C[MAX];
int fa[MAX];
inline void RMQ(int num){
	for(int i=1;i<=num;i++)
		maxx[i][0]=C[i],minn[i][0]=C[i];
	for(int j=1;j<20;++j)
		for(int i=1;i<=num;++i)
			if(i+(1<<j)-1<=num){
				maxx[i][j]=max(maxx[i][j-1],maxx[i+(1<<(j-1))][j-1]);
				minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]);
			}
}
int _max,_min;
inline void query(int L,int R){
	int k=(int)log2(double(R-L+1));
	int kd=1<<k;
	_max=max(maxx[L][k],maxx[R-kd+1][k]);
	_min=min(minn[L][k],minn[R-kd+1][k]);
}
inline void read(int& x){
	char c=getchar();
	while(c<'0'||c>'9')
		c=getchar();
	x=0;
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
}
int ind=0;
int ins[MAX]={0};
inline void tarjan(int x){
	dfn[x]=low[x]=++ind;
	ins[x]=1;
	s.push(x);
	for(int i=0;i<A[x].size();i++){
		int u=A[x][i];
		if(!dfn[u]){
			tarjan(u);
			low[x]=min(low[x],low[u]);
		}
		else if(ins[u])
			low[x]=min(low[x],dfn[u]);
	}
	if(dfn[x]==low[x]){
		fa[x]=x;
		int k;
		do{
			k=s.top();
			s.pop();
			fa[k]=x;
		}while(k!=x);
	}
}
int main(){
	freopen("basicgraph.in","r",stdin);
	freopen("basicgraph.out","w",stdout);
	int n;
	read(n);
	memset(maxx,0,sizeof(maxx));
	memset(minn,127,sizeof(minn));
	for(int i=1;i<=n;i++)
		read(C[i]);
	RMQ(n);
	int m;
	int x,y;
	read(m);
	for(int i=1;i<=m;i++){
		read(x);read(y);
		query(x,y);
		A[_max].push_back(_min);
		A[_min].push_back(_max);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])
			tarjan(i);
	int mm;
	read(mm);
	for(int i=1;i<=mm;i++){
		read(x),read(y);
		if(fa[x]==fa[y])
			printf("YES\n");
		else printf("NO\n");
	}
return 0;
}