Submission #924431

#TimeUsernameProblemLanguageResultExecution timeMemory
924431Jawad_Akbar_JJPolitical Development (BOI17_politicaldevelopment)C++17
4 / 100
3031 ms311376 KiB
#include <iostream> #include <vector> #include <bitset> using namespace std; const int N = 50005; vector<int> vec[N]; bitset<N> dsag[N]; void sub1(int n){ for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (dsag[i][j] == 1){ cout<<2<<endl; exit(0); } cout<<1<<endl; exit(0); } void sub2(int n){ for (int i=1;i<=n;i++){ for (int j=i+1;j<=n;j++){ if ((dsag[i][j] == 1) and (dsag[i] & dsag[j]) != dsag[0]){ cout<<3<<endl; exit(0); } } } sub1(n); } void sub3(int n){ int mx = 1; for (int i=1;i<=n;i++) dsag[i][i] = 1; for (int i=1;i<=n;i++){ int k = vec[i].size(); for (int mask = 1;mask < (1<<k);mask++){ int cnt = 0; dsag[0][i] = 1; for (int j = 0;j < k;j++) if ((1<<j) & mask) dsag[0][vec[i][j]] = 1,cnt++; bool t = true; for (int j = 0;j < k;j++) if ((1<<j) & mask and (dsag[vec[i][j]] & dsag[0]) != dsag[0]){ t = false; break; } if (t) mx = max(mx,cnt + 1); dsag[0] >>= N; } } cout<<mx<<endl; exit(0); } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n,k; cin>>n>>k; for (int i=1;i<=n;i++){ int k; cin>>k; while (k--){ int a; cin>>a; dsag[i][a + 1] = 1; vec[i].push_back(a+1); } } if (k == 1){ cout<<1<<endl; return 0; } // if (k == 2) // sub1(n); // if (k == 3) // sub2(n); sub3(n); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...