Advertisement
Guest User

Untitled

a guest
Jun 27th, 2017
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.55 KB | None | 0 0
  1. //BĄDŹ ELEGANCKI NAJWAŻNIEJSZA NIE JEST KASA
  2. //JP NA 100%
  3. #include <cstdio>
  4. #include <algorithm>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. bool kr[5010][5010];
  10. vector <short int> t[5010];
  11. pair<short int, short int> ta[5010];
  12. int stopi,il,posz,ak,ilw,pom,czy,wyn;
  13. bool odw[5010];
  14. bool zam[5010];
  15.  
  16. void wczytaj()
  17. {
  18.     scanf("%d",&il);
  19.     for (int i=1; i<=il; ++i)
  20.     {
  21.         scanf("%d",&stopi);
  22.         ta[i-1].first=stopi;
  23.         ta[i-1].second=i;
  24.         for (int j=1; j<=stopi; ++j)
  25.         {
  26.             scanf("%d",&posz);
  27.             kr[i][posz]=1;
  28.             t[i].push_back(posz);
  29.         }
  30.     }
  31. }
  32. void rob_maks_klike()
  33. {
  34.     sort(ta,ta+il);
  35.     ak=0;
  36.     while (odw[ta[ak].second]==0&&ak<il)
  37.     {
  38.           for (int i=0; i<t[ta[ak].second].size(); ++i)
  39.           if (odw[t[ta[ak].second][i]]==0)
  40.           {
  41.               odw[t[ta[ak].second][i]]=1;
  42.               ++ilw;
  43.           }
  44.           ++ak;
  45.     }
  46.     //if (ilw!=0)
  47.     for (int i=1; i<=il; ++i)
  48.     if (odw[i]==0)
  49.     {
  50.        // printf("%d\n",ta[i].second);
  51.         pom=0;
  52.         for (int j=0; j<t[i].size(); ++j)
  53.         if (odw[t[i][j]]==1) ++pom;
  54.         if (pom==ilw)
  55.         {
  56.                      odw[i]=1;
  57.                      ++ilw;
  58.         }
  59.     }
  60. }
  61. void usuwaj()
  62. {
  63.      for (int i=1; i<=il; ++i)
  64.      if(odw[i]==1)
  65.      {
  66.          czy=1;
  67.          for (int j=0; j<t[i].size(); ++j)
  68.          if (odw[t[i][j]]==0) {czy=0; break;}        
  69.          if (czy) {++wyn; zam[i]=1;}
  70.      }else
  71.      {
  72.          pom=0;
  73.          for (int j=0; j<t[i].size(); ++j)
  74.          if (odw[t[i][j]]==1) ++pom;
  75.          if (pom==ilw-1) zam[i]=1;
  76.      }
  77.      if (ilw==1) wyn=1;
  78. }
  79. void zilomazewspracialaczasiekonspiratorzy()
  80. {
  81.      for (int i=1; i<=il; ++i)
  82.      if (odw[i]==0)
  83.      {
  84.         pom=0;
  85.         for (int j=0; j<t[i].size(); ++j)
  86.         if (odw[t[i][j]]==1) ++pom;
  87.         if (pom==ilw-1) zam[i]=1;
  88.      }
  89. }
  90. void zamieniaj()
  91. {
  92.      for (int i=1; i<il; ++i)
  93.          for (int j=i+1; j<=il; ++j)
  94.          if (odw[i]+odw[j]==1&&zam[i]+zam[j]==2)
  95.          ++wyn; else
  96.          if ((odw[i]+odw[j]==0&&kr[i][j]==1)||(odw[i]+odw[j]==2&&kr[i][j]==0)) {wyn=0; return;}
  97. }
  98. int main()
  99. {
  100.    
  101.     wczytaj();
  102.     rob_maks_klike();
  103.     printf("");
  104.     if (ilw!=0){
  105.     //printf("%d\n",ilw);
  106.     if (ilw!=il) wyn=1;
  107.     usuwaj();
  108.     //zilomazewspracialaczasiekonspiratorzy();
  109.     //for (int i=1; i<=il; ++i)
  110.     //if (zam[i]==1) printf("%d ",i);
  111.     //printf("\n");        
  112.     zamieniaj();}
  113.     printf("%d\n",wyn);
  114.     //while (1);
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement