比赛 |
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;
}