fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. //three arrays to maintain the hierarchy, eats represents the root node of prey, eaten represents the root node of predator
  4. int dsu[60000],eats[60000],eaten[60000],siz[60000];
  5. //initialising function
  6. void init(int n){
  7.     for(int i=0;i<=n;i++){
  8.         dsu[i]=i;
  9.         eats[i]=eaten[i]=0;
  10.         siz[i]=1;
  11.     }
  12. }
  13. //typical compressed root find function
  14. int root_find(int x){
  15.     while(x!=dsu[x]){
  16.         dsu[x]=dsu[dsu[x]];
  17.         x=dsu[x];
  18.     }
  19.     return x;
  20. }
  21. int main(){
  22.     ios::sync_with_stdio(false);
  23.     cin.tie(0);
  24.     cout.tie(0);
  25.     int t,n,k,x,y,s,d;
  26.     cin>>t;
  27.     while(t--){
  28.         cin>>n>>k;
  29.         s=0;
  30.         init(n);
  31.         while(k--){
  32.             cin>>d>>x>>y;
  33.             //if x>n or y>n
  34.             if(x>n||y>n){
  35.                 s++;
  36.                 continue;
  37.             }
  38.             x=root_find(x);
  39.             y=root_find(y);
  40.             eats[x]=root_find(eats[x]);
  41.             eats[y]=root_find(eats[y]);
  42.             eaten[x]=root_find(eaten[x]);
  43.             eaten[y]=root_find(eaten[y]);
  44.         	//if x==y, nothing needs to be processed whatsoever  
  45.             if(d==1&&x!=y){
  46.                 if(eats[x]==eaten[y]&&eats[x]!=0)  //if prey of x is same as predator of y, and prey of x is not empty
  47.                     s++;
  48.                 else if(eats[y]==eaten[x]&&eats[y]!=0) //if prey of y is same as predator of x and predator of y is not empty
  49.                     s++;
  50.                 else if(eats[y]==x) //if prey of y is same as x
  51.                     s++;
  52.                 else if(eats[x]==y) //if prey of x is same as y
  53.                     s++;
  54.                 else if(eaten[x]==y) //if predator of x is same as y
  55.                     s++;
  56.                 else if(eaten[y]==x) //if predator of y is same as x
  57.                     s++;
  58.                 else{
  59.                 	//all possible contradictions are hereby covered
  60.                 	//now we combine (x,y) , (eats[x],eats[y]) & (eaten[x],eaten[y]) 
  61.                     if(siz[eats[x]]>=siz[eats[y]]&&eats[x]!=0&&eats[y]!=0){
  62.                         dsu[eats[y]]=eats[x];
  63.                         siz[eats[x]]+=siz[eats[y]];
  64.                     }
  65.                     else if(eats[x]!=0&&eats[y]!=0){
  66.                         dsu[eats[x]]=eats[y];
  67.                         siz[eats[y]]+=siz[eats[x]];
  68.                     }
  69.                     else if(eats[y]==0&&eats[x]!=0)
  70.                         eats[y]=x;
  71.                     else if(eats[x]==0&&eats[y]!=0)
  72.                         eats[x]=y;
  73.                     if(siz[eaten[x]]>=siz[eaten[y]]&&eaten[x]!=0&&eaten[y]!=0){
  74.                         dsu[eaten[y]]=eats[y];
  75.                         siz[eaten[y]]+=siz[eaten[x]];
  76.                     }
  77.                     else if(eaten[x]!=0&&eaten[y]!=0){
  78.                         dsu[eaten[x]]=eaten[y];
  79.                         siz[eaten[y]]+=siz[eaten[x]];
  80.                     }
  81.                     else if(eaten[y]==0&&eaten[x]!=0)
  82.                         eaten[y]=x;
  83.                     else if(eaten[x]==0&&eaten[y]!=0)
  84.                         eaten[x]=y;
  85.                     if(siz[x]>=siz[y]){
  86.                         siz[x]+=siz[y];
  87.                         dsu[y]=x;
  88.                     }
  89.                     else{
  90.                         siz[y]+=siz[x];
  91.                         dsu[x]=y;
  92.                     }
  93.                 }
  94.             }
  95.             else if(d==2&&eaten[y]!=x&&eats[x]!=y){
  96.                 //if x is same as y or y eats x
  97.                 if(x==y)
  98.                     s++;
  99.                 else if(eats[y]==x)
  100.                     s++;
  101.                 else if(eaten[x]==y)
  102.                     s++;
  103.                 else{
  104.                 	// combine (eats[x],y),(eats[y],eaten[x]) & (eaten[y],x)
  105.                     if(siz[eats[x]]>=siz[y]&&eats[x]!=0){
  106.                         siz[eats[x]]+=siz[y];
  107.                         dsu[y]=eats[x];
  108.                     }
  109.                     else if(eats[x]!=0){
  110.                         siz[y]+=siz[eats[x]];
  111.                         dsu[eats[x]]=y;
  112.                     }
  113.                     else
  114.                         eats[x]=y;
  115.                     if(siz[eaten[y]]>=siz[x]&&eaten[y]!=0){
  116.                         siz[eaten[y]]+=siz[x];
  117.                         dsu[x]=eaten[y];
  118.                     }
  119.                     else if(eaten[y]!=0){
  120.                         siz[x]+=siz[eaten[y]];
  121.                         dsu[eaten[y]]=x;
  122.                     }
  123.                     else
  124.                         eaten[y]=x;
  125.                     if(siz[eaten[x]]>=siz[eats[y]]&&eaten[x]!=0&&eats[y]!=0){
  126.                         siz[eaten[x]]+=siz[eats[y]];
  127.                         dsu[eats[y]]=eaten[x];
  128.                     }
  129.                     else if(eaten[x]!=0&&eats[y]!=0){
  130.                         siz[eats[y]]+=siz[eaten[x]];
  131.                         dsu[eaten[x]]=eaten[y];
  132.                     }
  133.                     else if(eaten[x]==0&&eats[y]!=0)
  134.                         eaten[x]=y;
  135.                     else if(eaten[x]!=0&&eats[y]==0)
  136.                         eats[y]=eaten[x];
  137.                 }
  138.             }
  139.         }
  140.         //all incorrect statements.
  141.         cout<<s<<"\n";
  142.     }
  143.     return 0;
  144. }
  145.  
Success #stdin #stdout 0s 4388KB
comments (?)
stdin
copy 
1
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
stdout
copy 
3
https://ideone.com/Egu19B
language:
C++14 (gcc 8.3)
created:
8 years 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!