# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
311108 | 2020-10-09T09:15:22 Z | Vladth11 | Political Development (BOI17_politicaldevelopment) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> #define debug(x) cerr << #x << " " << x << "\n" #define debug_with_space(x) cerr << #x << " " << x << " " using namespace std; typedef long long ll; typedef pair <ll, ll> pii; typedef pair <ll, pii> muchie; const ll NMAX = 100005; const ll INF = (1LL << 60); const ll MOD = 1000000007; const ll BLOCK = 101; vector <int> v[NMAX]; int st[NMAX]; int main() { // ifstream cin("catsfood.in"); // ofstream cout("catsfood.out"); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, k, i, d; cin >> n >> k; for(i = 1; i <= n; i++) { int d; cin >> d; v[i].push_back(i); while(d--) { int x; cin >> x; v[i].push_back(x + 1); } sort(v[i].begin(), v[i].end()); } int maxim = 0; for(i = 1; i <= n; i++) { int nrbits = v[i].size(); // debug(i); for(int mask = 1; mask < (1 << nrbits); mask++) { st.clear(); int cnt = 0; for(int j = nrbits - 1; j >= 0; j--) { if(mask & (1 << j)) { for(auto x : v[v[i][j]]) { if(st[x] != 0) cnt++; } st[v[i][j]] = 1; } } for(int j = 0; j < nrbits;j++) st[v[i][j]] = 0; int bb = __builtin_popcount(mask); // debug_with_space(mask); // debug(cnt); if(cnt == bb * (bb - 1) / 2) maxim = max(maxim, bb); } } cout << maxim; return 0; }