比赛 防止浮躁的小练习v0.5 评测结果 AAATAAT
题目名称 基本的图问题 最终得分 71
用户昵称 Kulliu 运行时间 2.118 s
代码语言 C++ 内存使用 1.07 MiB
提交时间 2016-10-15 16:53:30
显示代码纯文本
  1. /*************************
  2. Personal idea of level-1
  3. **************************/
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<cstring>
  7. #include<cstdlib>
  8. #include<cstdio>
  9. #include<cmath>
  10. using namespace std;
  11. #define INF 0x7fffffff
  12. typedef long long LL;
  13. const int SIZE = 100010;
  14.  
  15. int fa[SIZE],m,n,node[SIZE];//fmax[SIZE][SIZE],fmin[SIZE][SIZE];
  16.  
  17. int find(int x){
  18. if(fa[x]!=x)
  19. return fa[x]=find(fa[x]);
  20. return x;
  21. }
  22.  
  23. void Union(int u,int v){
  24. int fu=find(u),fv=find(v);
  25. fa[fu]=fv;
  26. }
  27.  
  28. void init(){
  29. int s,e;
  30. //memset(fmin,0x7f,sizeof(fmin));
  31. scanf("%d",&n);
  32. //scanf("%d",&node[i]);fmax[1][1]=fmin[1][1]=node[1];
  33. for(int i=1;i<=n;i++)scanf("%d",&node[i]),fa[i]=i;
  34. scanf("%d",&m);
  35. for(int i=1;i<=m;i++){
  36. scanf("%d%d",&s,&e);
  37. int max=0,min=INF;
  38. for(int j=s;j<=e;j++){
  39. if(node[j]>max)max=node[j];
  40. if(node[j]<min)min=node[j];
  41. }
  42. Union(max,min);
  43. }
  44. }
  45.  
  46. int main(){
  47. freopen("basicgraph.in","r",stdin);
  48. freopen("basicgraph.out","w",stdout);
  49. int k,x,y;
  50. init();
  51. scanf("%d",&k);
  52. while(k--)
  53. {
  54. scanf("%d%d",&x,&y);
  55. if(find(x)==find(y))printf("YES\n");
  56. else printf("NO\n");
  57. }
  58. fclose(stdin);fclose(stdout);
  59. return 0;
  60. }