fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<set>
  5. #include<iomanip>
  6. #include<queue>
  7. #include<cmath>
  8. #include<stack>
  9. #include <map> 
  10.  
  11. #define ll                   long long
  12. #define skip                 cin>>ws;
  13. #define vll                  vector<ll> 
  14. #define vi                   vector<int>
  15. #define vb                   vector<bool>
  16. #define vpll                 vector<pair<ll,ll>>
  17. #define vvll                 vector<vector<ll>>
  18. #define vvi                  vector<vector<int>>
  19. #define pll                  pair<ll,ll>
  20. #define vs                   vector<string>
  21. #define vvpll                vector<vector<pair<ll, ll>>>
  22. #define pb                   push_back
  23. #define pob                  pop_back()
  24. #define MOD                  (ll)(1e9)
  25. #define MOD2                 (ll)(998244353)
  26. #define INF                  (ll)(1e18 + 5)
  27. #define count1(n)            __builtin_popcountll(n)
  28. #define test                 ll t; cin>>t; while(t--)
  29. #define enter(a)             for(ll i=0;i<a.size();i++) cin>>a[i];
  30. #define show(a)              for(ll e: a) cout<<e<<" "; cout<<"\n";
  31.  
  32. using namespace std;
  33.  
  34. ll mo(ll a){ return a%MOD;}
  35.  
  36. ll po(ll x, ll y, ll p)
  37. {
  38.     ll res = 1; x = x % p;   
  39.     while (y > 0) { if (y & 1) res = (res * x) % p; y >>= 1; x = (x * x) % p; } 
  40.     return res%p; 
  41. }
  42.  
  43.  
  44. struct dsu
  45. {
  46.     int n;
  47.     vll a, rank, siz;
  48.  
  49.     void init(ll si)
  50.     {
  51.         n = si; 
  52.         a.resize(n); rank.resize(n); siz.assign(n, 1);
  53.         for(ll i=0;i<n;i++) 
  54.         {
  55.             rank[i] = 1; a[i] = i;
  56.         }
  57.     }
  58.  
  59.     ll get(ll i)
  60.     {
  61.         return a[i] = ((i==a[i])?i:get(a[i]));
  62.     }
  63.  
  64.     void unio(ll i, ll j)
  65.     {
  66.         ll x = get(i), y = get(j);
  67.         if(x==y) return;
  68.         if(rank[x]==rank[y]) rank[x]++;
  69.         if(rank[y]>rank[x]) swap(x, y);
  70.         a[y] = x;
  71.         siz[x] += siz[y];
  72.     }
  73.  
  74.     ll get_size(ll i)
  75.     {
  76.         return siz[get(i)];
  77.     }
  78. };
  79.  
  80. struct ed
  81. {
  82.     ll x, y;
  83. };
  84. struct query{
  85.     string q;
  86.     ll x,y;
  87. };
  88.  
  89. int main()
  90. {
  91.  
  92. //freopen("input.txt","r",stdin),freopen("output.txt","w",stdout);
  93.  
  94.     ios_base::sync_with_stdio(false);
  95.     cin.tie(NULL);
  96.  ll n,m,k;
  97.  cin>>n>>m>>k;
  98. ed edge[m+1];
  99. query qt[k+1];
  100. for(ll i=0;i<m;i++)
  101. {cin>>edge[i].x>>edge[i].y;}
  102. for(ll i=0;i<k;i++){
  103.     cin>>qt[i].q>>qt[i].x>>qt[i].y;
  104. }
  105.  
  106. dsu dt;
  107. vector<string > ans;
  108. dt.init(n);
  109. for(ll i=(k-1);i>=0;i--){
  110. string qy=qt[i].q;
  111. ll x=qt[i].x;
  112. ll y=qt[i].y;
  113. x--,y--;
  114. if(qy=="ask"){
  115.  
  116. //cout<<x<<" "<<y<<endl;
  117. if(dt.get(x)==dt.get(y)){
  118. ans.pb("YES");
  119.  
  120. }else{
  121.     ans.pb("NO");
  122. }}else{
  123.  
  124.  
  125. dt.unio(x,y);
  126. }
  127. }
  128.  
  129.  
  130.  for(ll i=ans.size()-1;i>=0;i--){
  131.     cout<<ans[i]<<endl;
  132.  }   
  133.  
  134.  //   cout<<ans<<"\n";
  135.  
  136.     return 0;
  137. }
Runtime error #stdin #stdout 0s 5652KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wodVCm
language:
C++14 (gcc 8.3)
created:
2 years 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!