| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 841259 | serifefedartar | Political Development (BOI17_politicaldevelopment) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 200005
vector<vector<int>> graph;
vector<pair<int,int>> degree;
set<pair<int,int>> edges;
bool omit[MAXN];
int main() {
fast
int N, K, x, D;
cin >> N >> K;
graph = vector<vector<int>>(N, vector<int>());
degree = vector<pair<int,int>>(N);
for (int i = 0; i < N; i++)
degree[i] = {0, i};
for (int i = 0; i < N; i++) {
cin >> D;
for (int j = 0; j < D; j++) {
cin >> x;
graph[x].push_back(i);
graph[i].push_back(x);
edges.insert({min(x, i), max(x, i)});
degree[i].f++;
degree[x].f++;
}
}
sort(degree.begin(), degree.end());
int ans = 1;
for (auto u : degree) {
int node = u.s;
vector<int> adj;
for (auto p : graph[node]) {
if (!omit[p])
adj.push_back(p);
}
int degree = adj.size();
int mx_mask = (1<<degree) - 1;
for (int msk = 1; msk <= mx_mask; msk++) {
vector<int> taken;
taken.push_back(node);
bool check = true;
for (int j = 0; j < degree; j++) {
if ((1<<j) & msk) {
for (auto u : taken) {
if (edges.count({min(adj[j], u), max(adj[j], u)}) == 0)
check = false;
}
taken.push_back(adj[j]);
}
}
if (check)
ans = max(ans, taken.size());
}
omit[node] = true;
}
cout << ans << "\n";
}