fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define fi first
  6. #define se second
  7. #define db double
  8. //#define int long long
  9. #define pb push_back
  10. #define FOR(i, a, b)    for (int i = (int)(a), lim(b); i <= lim; i++)
  11. #define FORD(i, a, b)   for (int i = (int)(a); i >= (int)(b); i--)
  12. #define MASK(i)     (1ll<<(i))
  13. #define c_bit(x)    __builtin_popcountll(x)
  14. #define BIT(x, i)   ((x) & MASK(i))
  15. #define set_on(x, i)    ((x) | MASK(i))
  16. #define set_off(x, i)   ((x) & ~MASK(i))
  17. #define TASK "R10BOND"
  18.  
  19. template <class X, class Y>
  20.     bool minimize(X &x, const Y &y)
  21.     {
  22.         if (x > y)
  23.         {
  24.             x = y;
  25.             return 1;
  26.         }
  27.         else return 0;
  28.     }
  29. template <class X, class Y>
  30.     bool maximize(X &x, const Y &y)
  31.     {
  32.         if (x < y)
  33.         {
  34.             x = y;
  35.             return 1;
  36.         }
  37.         else return 0;
  38.     }
  39. template <class T>
  40.     T Abs(const T &x)
  41.     {
  42.         return (x < 0 ? -x : x);
  43.     }
  44.  
  45. const int sm = 998244353, N = 100 + 5, M = 100005 ,  base = 311;
  46.  
  47. void add(int &x, const int &y)  {x += y; if (x > sm)    x -= sm;}
  48. void sub(int &x, const int &y)  {x -=y; if (x<0)  x+=sm;}
  49.  
  50. bool mtt = 0;
  51. int test = 1;
  52.  
  53. int m, n, q;
  54. pair<int, int> e[M], quest[M];
  55.  
  56. void doc()
  57. {
  58.     cin>>n>>m;
  59.     FOR(i, 1, m)    
  60.     {
  61.         int x, y;
  62.         cin>>x>>y;
  63.         e[i] = {x, y};
  64.     }
  65.     cin>>q;
  66.     FOR(i, 1, q)
  67.     {
  68.         cin>>quest[i].fi>>quest[i].se;
  69.     }
  70. }
  71.  
  72. namespace sub1
  73. {
  74.     int f[N], dk[M];
  75.  
  76.     bool check()
  77.     {
  78.         FOR(i, 1, q)
  79.         {
  80.             if (quest[i].fi > 100)   return 0;
  81.         }
  82.         return 1;
  83.     }
  84.     int goc(int u)
  85.     {
  86.         while (f[u] > 0)    u = f[u];
  87.         return u;
  88.     }
  89.     void HN(int r1, int r2)
  90.     {
  91.         int t = f[r1] + f[r2];
  92.         if (Abs(f[r1]) > Abs(f[r2]))
  93.         {
  94.             f[r1] = t;
  95.             f[r2] = r1;
  96.         }
  97.         else
  98.         {
  99.             f[r2] = t;
  100.             f[r1] = r2;
  101.         }
  102.     }
  103.     void xuly()
  104.     {
  105.         FOR(i, 1, n)    f[i] = -1;    
  106.         FOR(i, 1, 70)
  107.         {
  108.             int cnt = 0;
  109.             FOR(j, i, m)
  110.             {
  111.                 int r1 = goc(e[j].fi), r2 = goc(e[j].se);
  112.                 if (r1 != r2)
  113.                 {
  114.                     HN(r1, r2);
  115.                     cnt ++;
  116.                     if (cnt == n - 1)
  117.                     {
  118.                         dk[i] = j;
  119.                         break;
  120.                     }
  121.                 }
  122.             }
  123.             FOR(j, 1, n)    f[j] = -1;
  124.         }
  125.         FOR(i, 1, q)
  126.         {
  127.             int x = quest[i].fi, y = quest[i].se;
  128.             if (y < dk[x] or dk[x] == 0)  cout<<"No\n";
  129.             else cout<<"Yes\n";
  130.         }
  131.     }
  132. }
  133.  
  134. namespace sub2
  135. {
  136.     int f[N], dk[M], last[N];
  137.  
  138.     int goc(int u)
  139.     {
  140.         while (f[u] > 0)    u = f[u];
  141.         return u;
  142.     }
  143.     void HN(int r1, int r2)
  144.     {
  145.         int t = f[r1] + f[r2];
  146.         if (Abs(f[r1]) > Abs(f[r2]))
  147.         {
  148.             f[r1] = t;
  149.             f[r2] = r1;
  150.         }
  151.         else
  152.         {
  153.             f[r2] = t;
  154.             f[r1] = r2;
  155.         }
  156.     }
  157.  
  158.     void xuly()
  159.     {
  160.         FOR(i, 1, m)
  161.         {
  162.             FOR(j, 1, n)    f[j] = -1;
  163.             last[0] = i - 1;
  164.             FOR(j, 1, n - 1)
  165.             {
  166.                 int k = max(last[j - 1] + 1, last[j]);
  167.                 while (k <= m)
  168.                 {
  169.                     int r1 = goc(e[k].fi), r2 = goc(e[k].se);
  170.                     if (r1 == r2)
  171.                     {
  172.                         k ++;
  173.                     }
  174.                     else break;
  175.                 }
  176.                 int r1 = goc(e[k].fi), r2 = goc(e[k].se);
  177.                 HN(r1, r2);
  178.                 last[j] = k;
  179.                 if (j == n - 1)
  180.                 {
  181.                     dk[i] = k;
  182.                     break;
  183.                 }
  184.                 //k ++;
  185.             }
  186.  
  187.         }
  188.  
  189.         FOR(i, 1, q)
  190.         {
  191.             int x = quest[i].fi, y = quest[i].se;
  192.             if (y < dk[x] or dk[x] == 0)  cout<<"No\n";
  193.             else cout<<"Yes\n";
  194.         }
  195.     }
  196. }
  197.  
  198. signed main()
  199. {
  200.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  201.     if (fopen(TASK".INP", "r"))
  202.     {
  203.         freopen(TASK".INP", "r", stdin);
  204.         freopen(TASK".OUT", "w", stdout);
  205.     }
  206.     else if (fopen("INP.INP", "r"))
  207.     {
  208.         freopen("INP.INP", "r", stdin);
  209.         freopen("INP.OUT", "w", stdout);
  210.     }
  211.  
  212.     if (mtt)    cin>>test;
  213.     while (test--)
  214.     {
  215.         doc();
  216.         if (sub1::check())  sub1::xuly();
  217.         else sub2::xuly();
  218.     }
  219. }
Success #stdin #stdout 0s 5280KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/TRHF2H
language:
C++14 (gcc 8.3)
created:
150 days 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!