fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. const int N = 2e5 + 5;
  6. int n , m , t , B , o , r;
  7. bool heavy[N];
  8. bitset < N > b[3005];
  9. int ans[3005][3005];
  10. int mp[N] , cnt[N];
  11. bool f[N];
  12. set < int > g[N];
  13.  
  14. struct ed{
  15.     int u , v;
  16. }edge[N];
  17.  
  18. struct que{
  19.     int u , v , type;
  20. }q[N];
  21.  
  22. vector < int > h;
  23.  
  24. void add(int u , int v)
  25. {
  26.     if(g[u].find(v) == g[u].end())
  27.     {
  28.         if(heavy[u] == true && heavy[v] == true)
  29.         {
  30.             ans[mp[u]][mp[v]] = true;
  31.             ans[mp[v]][mp[u]] = true;
  32.             b[mp[u]][v] = true;
  33.             b[mp[v]][u] = true;
  34.  
  35.  
  36.             for(auto x: h)
  37.             {
  38.                 if(b[mp[u]][x] == true)
  39.                 {
  40.                     ans[mp[v]][mp[x]] = true;
  41.                     ans[mp[x]][mp[v]] = true;
  42.                 }
  43.                 if(b[mp[v]][x] == true)
  44.                 {
  45.                     ans[mp[u]][mp[x]] = true;
  46.                     ans[mp[x]][mp[u]] = true;
  47.                 }
  48.             }
  49.         }
  50.         else if(heavy[u] == true)
  51.         {
  52.             b[mp[u]][v] = true;
  53.             for(auto x: g[v])
  54.                 if(heavy[x])
  55.                 {
  56.                     ans[mp[u]][mp[x]] = true;
  57.                     ans[mp[x]][mp[u]] = true;
  58.                 }
  59.         }
  60.         else if(heavy[v] == true)
  61.         {
  62.             b[mp[v]][u] = true;
  63.             for(auto x: g[u])
  64.                 if(heavy[x])
  65.                 {
  66.                     ans[mp[v]][mp[x]] = true;
  67.                     ans[mp[x]][mp[v]] = true;
  68.                 }
  69.         }
  70.         g[u].insert(v);
  71.         g[v].insert(u);
  72.     }
  73. }
  74.  
  75. main()
  76. {
  77.     freopen("friends.inp","r",stdin);
  78.     freopen("friends.out","w",stdout);
  79.  
  80.     ios::sync_with_stdio(0);
  81.     cin.tie(0);
  82.     cin >> n >> m;
  83.  
  84.     for(int i = 1 ; i <= m ; i++)
  85.     {
  86.         cin >> edge[i].u >> edge[i].v;
  87.         cnt[edge[i].u]++;
  88.         cnt[edge[i].v]++;
  89.     }
  90.     cin >> t;
  91.     for(int i = 1 ; i <= t ; i++)
  92.     {
  93.         cin >> q[i].type >> q[i].u >> q[i].v;
  94.         if(q[i].type == 2)
  95.         {
  96.             cnt[edge[i].u]++;
  97.             cnt[edge[i].v]++;
  98.         }
  99.     }
  100.     int B = sqrt(m + t);
  101.     for(int i = 1 ; i <= n ; i++)
  102.         if(cnt[i] > B)
  103.         {
  104.             h.push_back(i);
  105.             heavy[i] = true;
  106.             mp[i] = ++r;
  107.         }
  108.  
  109.     for(int i = 1 ; i <= m ; i++)
  110.         add(edge[i].u , edge[i].v);
  111.  
  112.  
  113.     for(int i = 1 ; i <= t ; i++)
  114.     {
  115.         if(q[i].type == 1)
  116.             add(q[i].u , q[i].v);
  117.         else
  118.         {
  119.             bool check = false;
  120.             if(heavy[q[i].u] == false && heavy[q[i].v] == false)
  121.             {
  122.                 for(auto x: g[q[i].u])
  123.                 {
  124.                     f[x] = true;
  125.                     if(x == q[i].v)
  126.                     {
  127.                         check = true;
  128.                         break;
  129.                     }
  130.                 }
  131.  
  132.                 for(auto x: g[q[i].v])
  133.                     if(f[x])
  134.                     {
  135.                         check = true;
  136.                         break;
  137.                     }
  138.  
  139.                 for(auto x: g[q[i].u])
  140.                     f[x] = false;
  141.  
  142.             }
  143.             else if(heavy[q[i].u] == false)
  144.             {
  145.                 for(auto x: g[q[i].u])
  146.                 {
  147.                     f[x] = true;
  148.                     if(x == q[i].v || b[mp[q[i].v]][x])
  149.                     {
  150.                         check = true;
  151.                         break;
  152.                     }
  153.                 }
  154.                 for(auto x: g[q[i].u])
  155.                     f[x] =false;
  156.             }
  157.             else if(heavy[q[i].v] == false)
  158.             {
  159.                 for(auto x: g[q[i].v])
  160.                 {
  161.                     f[x] = true;
  162.                     if(x == q[i].u || b[mp[q[i].u]][x])
  163.                     {
  164.                         check = true;
  165.                         break;
  166.                     }
  167.                 }
  168.                 for(auto x: g[q[i].v])
  169.                     f[x] = false;
  170.             }
  171.             else
  172.             {
  173.                 if(ans[mp[q[i].u]][mp[q[i].v]] == true)
  174.                     check = true;
  175.             }
  176.             if(check)
  177.                 cout << "YES\n";
  178.             else
  179.                 cout << "NO\n";
  180.         }
  181.     }
  182.  
  183. }
  184.  
Success #stdin #stdout 0.01s 16084KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pGDKOj
language:
C++14 (gcc 8.3)
created:
12 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!