#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(abs(a), abs(b));}
ll lcm(ll a, ll b){return abs(a) / gcd(a, b) * abs(b);}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
// mt19937_64 rng(1);
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
const int N = 2525;
int n, p, q;
vector<int> graph[N];
vector<vector<int>> usable;
void dfs(vector<int> v, set<vector<int>> &S){
if (S.insert(v).second == false) return;
vector<int> adj;
for(int i: v)
for(int j: graph[i]) if (!binary_search(ALL(v), j))
adj.push_back(j);
remove_dup(adj);
if ((int)adj.size() <= q){
usable.push_back(v);
return;
}
if ((int)v.size() >= p) return;
for(int i: adj){
vector<int> _v = v;
_v.push_back(i);
remove_dup(_v);
vector<int> _adj = adj;
_adj.erase(lower_bound(ALL(_adj), i));
for(int j: graph[i]) if (!binary_search(ALL(_v), j))
_adj.push_back(j);
remove_dup(_adj);
if ((int)_v.size() + (int)_adj.size() > p + q) continue;
dfs(_v, S);
}
}
void solve(){
cin >> n >> p >> q;
for(int i = 0; i < n; ++i){
int m; cin >> m;
graph[i].resize(m);
for(int &j: graph[i]) cin >> j;
sort(ALL(graph[i]));
}
#define get_detention(){cout << "detention\n"; return;}
for(int i = 0; i < n; ++i)
if ((int)graph[i].size() >= p + q) get_detention();
for(int i = 0; i < n; ++i) {
for(int j: graph[i]){
if (!binary_search(ALL(graph[j]), i)){
get_detention();
}
}
}
set<vector<int>> S;
for(int i = 0; i < n; ++i){
vector<int> v = {i};
dfs(v, S);
}
vector<int> marked(n);
vector<vector<int>> ans;
for(auto i: usable){
bool check = false;
for(int j: i) if (!marked[j]){
marked[j] = 1;
check = true;
}
if (check) {
ans.push_back(i);
}
}
if (*min_element(ALL(marked)) == 0) get_detention();
for(int i = 0; i < (int) ans.size(); ++i) for(int j = i+1; j < (int) ans.size(); ++j){
vector<int> sigma;
for(int x: ans[j]) if (!binary_search(ALL(ans[i]), x)) sigma.push_back(x);
vector<int> adj;
for(int x: sigma) for(int y: graph[x]) if (!binary_search(ALL(sigma), y)) adj.push_back(y);
if (adj.size() <= q){
ans[j] = sigma;
}
else{
sigma.clear();
for(int x: ans[i]) if (!binary_search(ALL(ans[j]), x)) sigma.push_back(x);
ans[i] = sigma;
}
}
cout << "home\n";
int cnt = 0;
for(auto i: ans) cnt += (i.size() > 0);
cout << cnt << "\n";
for(auto i: ans){
if (i.size()){
cout << i.size() << " "; printArr(i);
}
}
}
int main(void){
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
clock_t start = clock();
solve();
cerr << "Time elapsed: " << clock() - start << "ms!\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |