fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #define loop(i,a,b) for(int i=a;i<b;i++)
  3. #define loopb(i,a,b) for(int i=a;i>=b;i--)
  4. #define loopm(i,a,b,step) for(int i=a;i<b;i+=step)
  5. #define loopbm(i,a,b,step) for(int i=a;i>=b;i-=step)
  6. #define pb(a) push_back(a)
  7. #define mp(a,b) make_pair(a,b)
  8. #define init(arr,val) memset(arr,val,sizeof(arr))
  9. #define INF 1000000007
  10. #define MOD 1000000007
  11. #define BINF 1000000000000000001
  12.  
  13. #define double long double
  14.  
  15. using namespace std;
  16.  
  17. const int N=2005;
  18. const int LGN=20;
  19. vector<int>g[N];
  20.  
  21. vector<int>dfstree[N];
  22. bool visited[N];
  23. void dfs(int s)
  24. {
  25.     visited[s]=true;
  26.     for(int v:g[s])
  27.     {
  28.         if(!visited[v])
  29.         {
  30.             dfstree[s].push_back(v);
  31.             dfs(v);
  32.         }
  33.     }
  34. }
  35.  
  36. int dp[LGN][N];
  37. int ht[N];
  38. void dfs1(int s,int p,int h=0)
  39. {
  40.     ht[s]=h;
  41.     dp[0][s]=p;
  42.     loop(i,1,LGN) dp[i][s]=dp[i-1][dp[i-1][s]];
  43.     for(int v:dfstree[s])
  44.     {
  45.         dfs1(v,s,h+1);
  46.     }
  47. }
  48.  
  49. int walk(int s,int k)
  50. {
  51.     loop(i,0,LGN)
  52.     {
  53.         if(k&(1<<i)) s=dp[i][s];
  54.     }
  55.     return s;
  56. }
  57.  
  58. int lca(int x,int y)
  59. {
  60.     if(ht[x]<ht[y]) swap(x,y);
  61.     x=walk(x,ht[x]-ht[y]);
  62.     if(x==y) return x;
  63.     while(1)
  64.     {
  65.         bool flag=true;
  66.         loopb(i,LGN-1,0)
  67.         {
  68.             if(dp[i][x]!=dp[i][y])
  69.             {
  70.                 flag=false;
  71.                 x=dp[i][x];
  72.                 y=dp[i][y];
  73.             }
  74.         }
  75.         if(flag) break;
  76.     }
  77.     return dp[0][x];
  78. }
  79.  
  80. int num_nodes(int x,int y)
  81. {
  82.     int l=lca(x,y);
  83.     int uu=ht[x];
  84.     int vv=ht[y];
  85.     int ww=ht[l];
  86.     return uu+vv-2*ww+1;
  87. }
  88.  
  89. int par[N];
  90.  
  91.  
  92. bool dfs2(int s)
  93. {
  94.     bool ans=false;
  95.     visited[s]=true;
  96.     for(int v:g[s])
  97.     {
  98.         if(!visited[v])
  99.         {
  100.             par[v]=s;
  101.             ans|=dfs2(v);
  102.         }
  103.         else
  104.         {
  105.             if(par[s]==v) continue;
  106.             else
  107.             {
  108.                 int x=num_nodes(s,v);
  109.  
  110.                 if(x%2==1) ans=true;
  111.             }
  112.         }
  113.     }
  114.     return ans;
  115. }
  116.  
  117.  
  118. int main()
  119. {
  120.  
  121.  
  122.     int t;
  123.     scanf("%d",&t);
  124.     loop(query,1,t+1)
  125.     {
  126.         printf("Scenario #%d:\n",query);
  127.         int n,m;
  128.         scanf("%d %d",&n,&m);
  129.  
  130.         map<pair<int,int>,int>xxx;
  131.         loop(i,0,N)
  132.         {
  133.             g[i].clear();
  134.             dfstree[i].clear();
  135.             visited[i]=false;
  136.             ht[i]=0;
  137.             par[i]=0;
  138.             loop(j,0,LGN) dp[j][i]=0;
  139.         }
  140.  
  141.         loop(i,0,m)
  142.         {
  143.             int u,v;
  144.             scanf("%d %d",&u,&v);
  145.             g[u].push_back(v);
  146.             g[v].push_back(u);
  147.  
  148.  
  149.         }
  150.  
  151.  
  152.         loop(i,1,n+1)
  153.         {
  154.             if(!visited[i])
  155.               dfs(i);
  156.         }
  157.         loop(i,1,n+1){
  158.         if(par[i]==0)
  159.         dfs1(i,0);
  160.         }
  161.  
  162.         loop(i,0,N) visited[i]=false;
  163.         bool ans=false;
  164.         loop(i,1,n+1){
  165.         if(!visited[i])
  166.          ans|=dfs2(i);
  167.         }
  168.         if(ans==true) printf("Suspicious bugs found!\n");
  169.         else printf("No suspicious bugs found!\n");
  170.  
  171.     }
  172.     return 0;
  173. }
Success #stdin #stdout 0s 4488KB
comments (?)
stdin
copy 
2
3 3
1 2
2 3
1 3
4 2
1 2
3 4
stdout
copy 
Scenario #1:
Suspicious bugs found!
Scenario #2:
No suspicious bugs found!
https://ideone.com/TjQqwB
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

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!