fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=1e5+5;
  4. int timer=0;
  5. int low[N],num[N],tout[N],dep[N],p[N][20];
  6. bool joint[N];
  7. vector<int> adj[N];
  8. void calc(int n)
  9. {
  10.     p[1][0]=1;
  11.     for(int j=1;j<=19;j++){
  12.         for(int i=1;i<=n;i++){
  13.             p[i][j]=p[p[i][j-1]][j-1];
  14.         }
  15.     }
  16. }
  17. int find_par(int u,int par)
  18. {
  19.     for(int i=19;i>=0;i--){
  20.         if(dep[p[u][i]]>dep[par]) u=p[u][i];
  21.     }
  22.     return u;
  23. }
  24. void dfs(int u,int a)
  25. {
  26.     int ch=0;
  27.     low[u]=num[u]=++timer;
  28.     for(int v:adj[u]){
  29.         if(v==a) continue;
  30.         if(!num[v]){
  31.             ch++;
  32.             p[v][0]=u;
  33.             dep[v]=dep[u]+1;
  34.             dfs(v,u);
  35.             low[u]=min(low[u],low[v]);
  36.             if(u==a){
  37.                 if(ch>1) joint[u]=1;
  38.             }
  39.             else{
  40.                 if(low[v]>=num[u]) joint[u]=1;
  41.             }
  42.         }
  43.         else low[u]=min(low[u],num[v]);
  44.     }
  45.     tout[u]=timer;
  46. }
  47. bool check_subtree(int u,int r)
  48. {
  49.     return num[r]<=num[u]&&num[u]<=tout[r];
  50. }
  51. bool query1(int a,int b,int g1,int g2)
  52. {
  53.     if(num[g1]>num[g2]) swap(g1,g2);
  54.     if(low[g2]!=num[g2]) return 1;
  55.     if(check_subtree(a,g2)&&!check_subtree(b,g2)) return 0;
  56.     if(check_subtree(b,g2)&&!check_subtree(a,g2)) return 0;
  57.     return 1;
  58. }
  59. bool query2(int a,int b,int c)
  60. {
  61.     if(!joint[c]) return 1;
  62.     int pa=0,pb=0;
  63.     if(check_subtree(a,c)) pa=find_par(a,c);
  64.     if(check_subtree(b,c)) pb=find_par(b,c);
  65.     if(!pa&&!pb) return 1;
  66.     if(pa==pb) return 1;
  67.     if(!pa&&low[pb]<num[c]) return 1;
  68.     if(!pb&&low[pa]<num[c]) return 1;
  69.     if(pa&&pb&&low[pa]<num[c]&&low[pb]<num[c]) return 1;
  70.     return 0;
  71. }
  72. int main()
  73. {
  74.     ios_base::sync_with_stdio(false);
  75.     cin.tie(0);
  76.     cout.tie(0);
  77.     int n,m;
  78.     cin>>n>>m;
  79.     for(int a=0;a<m;a++){
  80.         int x,y;
  81.         cin>>x>>y;
  82.         adj[x].push_back(y);
  83.         adj[y].push_back(x);
  84.     }
  85.     dep[1]=1;
  86.     dfs(1,1);
  87.     calc(n);
  88.     int q;
  89.     cin>>q;
  90.     while(q--){
  91.         int type;
  92.         cin>>type;
  93.         if(type==1){
  94.             int a,b,g1,g2;
  95.             cin>>a>>b>>g1>>g2;
  96.             if(query1(a,b,g1,g2)) cout<<"yes\n";
  97.             else cout<<"no\n";
  98.         }
  99.         else{
  100.             int a,b,c;
  101.             cin>>a>>b>>c;
  102.             if(query2(a,b,c)) cout<<"yes\n";
  103.             else cout<<"no\n";
  104.         }
  105.     }
  106. }
  107.  
Success #stdin #stdout 0.01s 8200KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
yes
https://ideone.com/3onnTC
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!