fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long MaxN = 1e5 +5;
  4. long long n,q;
  5. struct DSU
  6. {
  7.     long long lab[3*MaxN];
  8.     void init()
  9.     {
  10.         for (long long i=1; i<=2*n+1; i++)
  11.         {
  12.             lab[i]=-1;
  13.         }
  14.     }
  15.     long long get_root(long long u)
  16.     {
  17.         if(lab[u]<0) return u;
  18.         return lab[u]=get_root(lab[u]);
  19.     }
  20.     void unite(long long u , long long v)
  21.     {
  22.         long long x = get_root(u), y=get_root(v);
  23.         if(x==y)
  24.         {
  25.             return;
  26.         }
  27.         if(lab[x]>lab[y]) swap(x,y);
  28.         lab[x]+=lab[y];
  29.         lab[y]=x;
  30.         return;
  31.     }
  32.     bool check(long long u, long long v)
  33.     {
  34.         return get_root(u)==get_root(v);
  35.     }
  36.     long long get_size(long long u)
  37.     {
  38.         return -lab[get_root(u)];
  39.     }
  40. };
  41. DSU dsu;
  42. struct QUERY
  43. {
  44.     long long num;
  45.     long long u;
  46.     long long v;
  47. };
  48. QUERY query[MaxN];
  49. void input()
  50. {
  51.     cin >> n >>q;
  52.     for (long long i=1; i<=q; i++)
  53.     {
  54.         cin >> query[i].num >> query[i].u >> query[i].v;
  55.     }
  56. }
  57. void solve()
  58. {
  59.     dsu.init();
  60.     for (long long i=1; i<=q; i++)
  61.     {
  62.         long long num = query[i].num;
  63.         long long u = query[i].u;
  64.         long long v = query[i].v;
  65.         if(num==1)
  66.         {
  67.             dsu.unite(u,v+n);
  68.             dsu.unite(v,u+n);
  69.         }
  70.         else
  71.         {
  72.             if(dsu.get_root(u)==dsu.get_root(v+n))
  73.             {
  74.                 cout << "FATAL" << "\n";
  75.             }
  76.             else if(dsu.get_root(u)==dsu.get_root(v))
  77.             {
  78.                 cout << "SAFE" << "\n";
  79.             }
  80.             else
  81.             {
  82.                 cout << "DUNNO" << "\n";
  83.             }
  84.         }
  85.     }
  86.  
  87. }
  88. int main()
  89. {
  90.     ios_base::sync_with_stdio(0);
  91.     cin.tie(0);
  92.     input();
  93.     solve();
  94. }
Success #stdin #stdout 0s 5780KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CA0FwW
language:
C++14 (gcc 8.3)
created:
1 day 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!