#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>
using namespace std;
typedef long long llong;
void fail() {
printf("detention\n");
exit(0);
}
int n, p, q;
vector<int> edge[2500];
int con[2500][2500];
vector<int> group[2500];
bool in[2500];
bool ex[2500];
bool backtrack(vector<int> &ret, int it = 0, int jt = 0, int np = 1, int nq = 0) {
if (p < np || q < nq) return 0;
while (it < ret.size()) {
while (jt < edge[ret[it]].size()) {
int x = edge[ret[it]][jt];
if (!in[x] && !ex[x]) {
++jt;
if (jt == edge[ret[it]].size()) ++it, jt = 0;
{
int nxp = np, nxq = nq;
in[x] = 1;
ret.push_back(x);
for (int i : edge[x]) {
if (in[i]) ++nxp;
if (ex[i]) ++nxq;
}
if (backtrack(ret, it, jt, nxp, nxq))
return 1;
in[x] = 0;
ret.pop_back();
}
{
int nxp = np, nxq = nq;
ex[x] = 1;
for (int i : edge[x]) {
if (in[i]) ++nxq;
}
if (backtrack(ret, it, jt, nxp, nxq))
return 1;
ex[x] = 0;
}
return 0;
}
++jt;
}
++it;
jt = 0;
}
return 1;
}
void pre_process() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
in[j] = ex[j] = 0;
in[i] = 1;
group[i].push_back(i);
if (!backtrack(group[i])) fail();
}
}
int st[2500];
void solve() {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
for (int k : group[i]) st[k] |= 1;
vector<int> gs;
for (int k : group[j]) {
st[k] |= 2;
if (st[k] == 3) gs.push_back(k);
}
int c1 = 0, c2 = 0;
for (int k : gs) {
for (int l : edge[k]) {
if (st[l] == 1) ++c1;
if (st[l] == 2) ++c2;
}
}
if (c1 < c2) {
vector<int> ns;
for (int k : group[i]) if (st[k] == 1)
ns.push_back(k);
group[i] = ns;
}
else {
vector<int> ns;
for (int k : group[j]) if (st[k] == 2)
ns.push_back(k);
group[j] = ns;
}
for (int k : group[i]) st[k] = 0;
for (int k : group[j]) st[k] = 0;
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> p >> q;
{
int one_cnt = 0;
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
while (k--) {
int x;
cin >> x;
if (con[i][x] == 1) --one_cnt;
if (++con[i][x] == 1) ++one_cnt;
++con[x][i];
edge[i].push_back(x);
}
}
if (one_cnt > 0) fail();
}
for (int i = 0; i < n; ++i) {
if (p + q <= edge[i].size()) fail();
}
pre_process();
solve();
printf("home\n");
int cnt = 0;
for (int i = 0; i < n; ++i) if (!group[i].empty())
++cnt;
printf("%d\n", cnt);
for (int i = 0; i < n; ++i) {
if (group[i].empty()) continue;
sort(group[i].begin(), group[i].end());
printf("%u", group[i].size());
for (int j : group[i]) printf(" %d", j);
printf("\n");
}
return 0;
}
Compilation message
friends.cpp: In function 'bool backtrack(std::vector<int>&, int, int, int, int)':
friends.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (it < ret.size()) {
~~~^~~~~~~~~~~~
friends.cpp:24:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (jt < edge[ret[it]].size()) {
~~~^~~~~~~~~~~~~~~~~~~~~~
friends.cpp:28:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (jt == edge[ret[it]].size()) ++it, jt = 0;
~~~^~~~~~~~~~~~~~~~~~~~~~~
friends.cpp: In function 'int main()':
friends.cpp:127:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (p + q <= edge[i].size()) fail();
~~~~~~^~~~~~~~~~~~~~~~~
friends.cpp:139:37: warning: format '%u' expects argument of type 'unsigned int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
printf("%u", group[i].size());
~~~~~~~~~~~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1272 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
1272 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Incorrect |
2 ms |
504 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
