//Challenge: Accepted
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <cmath>
#include <assert.h>
#include <unordered_set>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
//using namespace __gnu_pbds;
void debug() {cout << endl;}
template <class T, class ...U> void debug(T a, U ... b) { cout << a << " "; debug(b...);}
template <class T> void pary(T l, T r) {
while (l != r) {cout << *l << " ";l++;}
cout << endl;
}
#define ll long long
#define ld long double
#define maxn 50005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
unordered_set<int> ed[maxn];
int ord[maxn], deg[maxn], found[maxn], g[15];
int ans = 0;
int getans(int s, int cur, int ind, int se) {
if (ind >= s) return 0;
int ret = 0;
for (int v = ind;v < s;v++) {
if (((g[v] & se) & (cur | (1<<v))) == (cur | (1<<v))) {
ret = max(ret, getans(s, cur | (1<<v), v + 1, g[v] & se) + 1);
}
}
return ret;
}
void solve(int n) {
vector<int> se;
se.push_back(n);
for (int v:ed[n]) {
if (!found[v]) se.push_back(v);
}
//pary(se.begin(), se.end());
if (se.size() <= ans) return;
for (int i = 0;i < se.size();i++) {
g[i] = 0;
for (int j = i;j < se.size();j++) {
if (i == j) g[i] += 1<<i;
else {
int v = ed[se[i]].find(se[j]) == ed[se[i]].end() ? 0 : 1;
//debug(se[i], se[j], v);
g[i] += (1<<j) * v;
g[j] += (1<<i) * v;
}
}
}
//pary(g, g + se.size());
ans = max(ans, getans(se.size(), 0, 0, (1<<se.size()) - 1));
}
int main() {
io
int n, k;
cin >> n >> k;
for (int i = 0;i < n;i++) {
int di;
cin >> di;
deg[i] = di;
for (int j = 0;j < di;j++) {
int x;cin >> x;
ed[i].insert(x);
}
}
queue<int> que;
for (int i = 0;i < n;i++) {
if (deg[i] < k) {
que.push(i); found[i] = 1;
}
}
int ind = 0;
while (que.size()) {
int cur = que.front();que.pop();
ord[ind++] = cur;
for (int v:ed[cur]) {
if (--deg[v] < k && !found[v]) {
que.push(v);found[v] = 1;
}
}
}
for (int i = 0;i < n;i++) found[i] = 0;
for (int i = 0;i < n;i++) solve(ord[i]), found[ord[i]] = 1;
cout << ans << endl;
}
/*
5 3
2 1 2
3 0 2 3
3 0 1 4
2 1 4
2 2 3
*/
Compilation message
politicaldevelopment.cpp: In function 'void solve(int)':
politicaldevelopment.cpp:49:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
49 | if (se.size() <= ans) return;
| ~~~~~~~~~~^~~~~~
politicaldevelopment.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int i = 0;i < se.size();i++) {
| ~~^~~~~~~~~~~
politicaldevelopment.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for (int j = i;j < se.size();j++) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3020 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3020 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
