#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N, P, Q;
cin >> N >> P >> Q;
const auto Impossible = [&]() {
cout << "detention\n";
exit(0);
};
vector<vector<int>> adj(N);
vector<vector<int>> mat(N, vector<int>(N));
for (int i = 0; i < N; i++) {
int p;
cin >> p;
while (p--) {
int j;
cin >> j;
mat[i][j] = 1;
adj[i].emplace_back(j);
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (mat[i][j] != mat[j][i]) {
Impossible();
}
}
}
// Solution:
// Consider finding a group for a node u. For every node v
// not adjacent to u, we don't need to consider them (since
// it will only increase Q unnecessarily). For every node v
// adjacent to u, either we pick v (and increase current p)
// or we don't pick v (and increase current q). This way,
// we have around 2^{P + Q} total options.
//
// We find a group for every node u. This runs in O(N (P + Q) 2^{P + Q}).
// Then, for every pair of nodes, consider the 2 groups of these
// nodes. If they arent' disjoint, we want to split them so they
// are. We can note that:
//
// p1, p2 <= P, q1, q2 <= Q
// Let p3 = intersection of (p1, p2).
// Then:
// q1 + edges[p1][p3] <= Q
// q2 + edges[p3][p2] <= Q.
// So, min(q1 + edges[p3][p2], q2 + edges[p1][p3]) <= Q.
//
// So, we can always split them into disjoint groups. We repair
// all groups this way in O(N^2 * (P + Q)).
//
// Time complexity: O(N * (P + Q) * (N + 2^{P + Q})).
vector<int> cur;
vector<int> state;
const auto GetGroup = [&](const auto &self, int cur_head, int ptr, int p, int q, vector<int> &res) {
if (p > P || q > Q) return;
if (!res.empty()) return;
if (cur_head == p) { // found group
res = cur;
return;
}
int u = cur[cur_head];
if (adj[u].size() == ptr) {
return self(self, cur_head + 1, 0, p, q, res);
}
int v = adj[u][ptr];
if (state[v] == 0) { // v is undecided
state[v] = -1;
self(self, cur_head, ptr + 1, p, q + 1, res);
state[v] = +1;
cur.emplace_back(v);
self(self, cur_head, ptr + 1, p + 1, q, res);
cur.pop_back();
state[v] = 0;
} else if (state[v] == -1) { // we already decided not to pick this node
return self(self, cur_head, ptr + 1, p, q + 1, res);
} else if (state[v] == +1) { // we already picked this node in group
return self(self, cur_head, ptr + 1, p, q, res);
}
};
vector<vector<int>> inGroup(N);
for (int u = 0; u < N; u++) {
state.assign(N, 0);
cur = {u};
state[u] = 1;
GetGroup(GetGroup, 0, 0, 1, 0, inGroup[u]);
if (inGroup[u].empty()) {
Impossible();
}
}
const auto NoIntersection = [&](const vector<int> &A, const vector<int> &B) {
static vector<int> who(N);
for (auto i : A) who[i] = 0;
for (auto i : B) who[i] = 0;
for (auto i : A) who[i] |= 1;
for (auto i : B) who[i] |= 2;
for (auto i : A) if (who[i] == 3) return false;
for (auto i : B) if (who[i] == 3) return false;
return true;
};
const auto FixGroup = [&](int x, int y) {
static vector<int> who(N);
for (auto i : inGroup[x]) who[i] = 0;
for (auto i : inGroup[y]) who[i] = 0;
for (auto i : inGroup[x]) who[i] |= 1;
for (auto i : inGroup[y]) who[i] |= 2;
vector<int> xA, yA;
vector<int> xB, yB;
for (auto i : inGroup[x]) {
if (who[i] == 1) {
xA.emplace_back(i);
xB.emplace_back(i);
} else {
xA.emplace_back(i);
}
}
for (auto i : inGroup[y]) {
if (who[i] == 2) {
yA.emplace_back(i);
yB.emplace_back(i);
} else {
yA.emplace_back(i);
}
}
if (NoIntersection(xA, yB)) {
inGroup[x] = xA;
inGroup[y] = yB;
} else if (NoIntersection(xB, yA)) {
inGroup[x] = xB;
inGroup[y] = yA;
} else {
return false;
}
return true;
};
state.assign(N, 0);
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
assert(FixGroup(i, j));
}
}
vector<vector<int>> answer;
for (int i = 0; i < N; i++) {
if (!inGroup[i].empty()) {
answer.emplace_back(inGroup[i]);
}
}
cout << "home\n";
cout << answer.size() << '\n';
for (auto &a : answer) {
sort(begin(a), end(a));
cout << a.size();
for (auto i : a) cout << ' ' << i;
cout << '\n';
}
return 0;
}
Compilation message
friends.cpp: In instantiation of 'main()::<lambda(const auto:23&, int, int, int, int, std::vector<int>&)> [with auto:23 = main()::<lambda(const auto:23&, int, int, int, int, std::vector<int>&)>]':
friends.cpp:99:46: required from here
friends.cpp:74:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
74 | if (adj[u].size() == ptr) {
| ~~~~~~~~~~~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
11 ms |
452 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
432 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
11 ms |
452 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
432 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
