Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //BĄDŹ ELEGANCKI NAJWAŻNIEJSZA NIE JEST KASA
- //JP NA 100%
- #include <cstdio>
- #include <algorithm>
- #include <vector>
- using namespace std;
- bool kr[5010][5010];
- vector <short int> t[5010];
- pair<short int, short int> ta[5010];
- int stopi,il,posz,ak,ilw,pom,czy,wyn;
- bool odw[5010];
- bool zam[5010];
- void wczytaj()
- {
- scanf("%d",&il);
- for (int i=1; i<=il; ++i)
- {
- scanf("%d",&stopi);
- ta[i-1].first=stopi;
- ta[i-1].second=i;
- for (int j=1; j<=stopi; ++j)
- {
- scanf("%d",&posz);
- kr[i][posz]=1;
- t[i].push_back(posz);
- }
- }
- }
- void rob_maks_klike()
- {
- sort(ta,ta+il);
- ak=0;
- while (odw[ta[ak].second]==0&&ak<il)
- {
- for (int i=0; i<t[ta[ak].second].size(); ++i)
- if (odw[t[ta[ak].second][i]]==0)
- {
- odw[t[ta[ak].second][i]]=1;
- ++ilw;
- }
- ++ak;
- }
- //if (ilw!=0)
- for (int i=1; i<=il; ++i)
- if (odw[i]==0)
- {
- // printf("%d\n",ta[i].second);
- pom=0;
- for (int j=0; j<t[i].size(); ++j)
- if (odw[t[i][j]]==1) ++pom;
- if (pom==ilw)
- {
- odw[i]=1;
- ++ilw;
- }
- }
- }
- void usuwaj()
- {
- for (int i=1; i<=il; ++i)
- if(odw[i]==1)
- {
- czy=1;
- for (int j=0; j<t[i].size(); ++j)
- if (odw[t[i][j]]==0) {czy=0; break;}
- if (czy) {++wyn; zam[i]=1;}
- }else
- {
- pom=0;
- for (int j=0; j<t[i].size(); ++j)
- if (odw[t[i][j]]==1) ++pom;
- if (pom==ilw-1) zam[i]=1;
- }
- if (ilw==1) wyn=1;
- }
- void zilomazewspracialaczasiekonspiratorzy()
- {
- for (int i=1; i<=il; ++i)
- if (odw[i]==0)
- {
- pom=0;
- for (int j=0; j<t[i].size(); ++j)
- if (odw[t[i][j]]==1) ++pom;
- if (pom==ilw-1) zam[i]=1;
- }
- }
- void zamieniaj()
- {
- for (int i=1; i<il; ++i)
- for (int j=i+1; j<=il; ++j)
- if (odw[i]+odw[j]==1&&zam[i]+zam[j]==2)
- ++wyn; else
- if ((odw[i]+odw[j]==0&&kr[i][j]==1)||(odw[i]+odw[j]==2&&kr[i][j]==0)) {wyn=0; return;}
- }
- int main()
- {
- wczytaj();
- rob_maks_klike();
- printf("");
- if (ilw!=0){
- //printf("%d\n",ilw);
- if (ilw!=il) wyn=1;
- usuwaj();
- //zilomazewspracialaczasiekonspiratorzy();
- //for (int i=1; i<=il; ++i)
- //if (zam[i]==1) printf("%d ",i);
- //printf("\n");
- zamieniaj();}
- printf("%d\n",wyn);
- //while (1);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement