fork download 
  1.     #include <bits/stdc++.h>
  2.     #define ll long long
  3.     using namespace std;
  4.    struct DSU{   
  5.     vector<int>parent,gsize,minimal,maximal,score;
  6.     int comps;
  7.     int mxcmp;
  8.     DSU(int maxi){
  9.         score=parent=gsize=minimal=maximal=vector<int>(maxi+5);
  10.         comps=maxi;
  11.         mxcmp=1;
  12.         for(int i=0;i<=maxi;i++){
  13.            minimal[i]=maximal[i]=parent[i]=i,gsize[i]=1,score[i]=0;
  14.         }
  15.         }
  16.         int find_leader(int node){
  17.             return parent[node]=(parent[node]==node?node:find_leader(parent[node]));
  18.         }
  19.         bool samel(int node1,int node2){
  20.             return find_leader(node1)==find_leader(node2);
  21.         }
  22.         void union_set(int node1,int node2){
  23.             int u=find_leader(node1),v=find_leader(node2);
  24.             if(u==v)return;
  25.             if(gsize[u]<gsize[v])swap(u,v);
  26.             gsize[u]+=gsize[v],parent[v]=u;
  27.             score[v]-=score[u];
  28.             comps--;
  29.             mxcmp=max(gsize[u],mxcmp);
  30.             maximal[u]=max(maximal[u],maximal[v]);
  31.            minimal[u]=min(minimal[u],minimal[v]);
  32.         }
  33.         void cut(int node1,int node2){
  34.             int u=find_leader(node1),v=find_leader(node2);
  35.             if(u==v)
  36.             parent[node1]=node1;
  37.         }
  38.         int find_min(int u){
  39.             int v=find_leader(u);
  40.             return minimal[v];
  41.         }
  42.         int find_max(int u){
  43.             int v=find_leader(u);
  44.             return maximal[v];
  45.         }
  46.         int largest_comp(){
  47.             return mxcmp;
  48.         }
  49.         void score_update(int u,int x){
  50.            int v=find_leader(u);
  51.            score[v]+=x;
  52.         }
  53.         int get_score(int u){
  54.             int v=find_leader(u);
  55.             int ans=(v==u?score[v]:score[v]+score[u]);
  56.             return ans;
  57.         }
  58.     };
  59.      int main(){
  60.         int n,k,m;
  61.         cin>>n>>k>>m;
  62.         DSU dsu(n);
  63.         vector<pair<int,int>>a(k);
  64.         map<pair<int,int>,int>mp;
  65.         for(int i=0;i<k;i++){
  66.             int x,y;
  67.             cin>>x>>y;
  68.             if(x>y)swap(x,y);
  69.             a[i]={x,y};
  70.             mp[{x,y}]=i;
  71.         }
  72.         vector<bool>survived(k,1);
  73.         vector<pair<string,pair<int,int>>>qs(m);
  74.         for(int i=0;i<m;i++){
  75.             string s;
  76.             cin>>s;
  77.             int x,y;
  78.             cin>>x>>y;
  79.             qs[i]={s,{x,y}};
  80.             if(s=="cut"){
  81.                if(x>y)swap(x,y);
  82.             auto it=mp.find({x,y});
  83.             if(it!=mp.end()){
  84.                 survived[mp[{x,y}]]=0;
  85.             }
  86.             }
  87.         }
  88.         for(int i=0;i<k;i++){
  89.             if(survived[i]){
  90.                 dsu.union_set(a[i].first,a[i].second);
  91.             }
  92.         }
  93.         vector<string>ans;
  94.         for(int i=qs.size()-1;i>=0;i--){
  95.                if(qs[i].first=="ask"){
  96.                 bool is=dsu.samel(qs[i].second.first,qs[i].second.second);
  97.                 string k=(is?"YES\n":"NO\n");
  98.                 ans.push_back(k);
  99.                }
  100.                else{
  101.                 dsu.union_set(qs[i].second.first,qs[i].second.second);
  102.                }
  103.         }
  104.         reverse(ans.begin(),ans.end());
  105.         for(int i=0;i<ans.size();i++){
  106.             cout<<ans[i];
  107.         }
  108.         return 0;
  109.     }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/TNYVYd
language:
C++14 (gcc 8.3)
created:
10 hours 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!