//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,null_type,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 3e3 + 5;
const double eps = 1e-9;
bool mrk[MAXN][MAXN];
vi adj[MAXN];
ht arr[MAXN];
int n, p, q;
bool valid(ht& a) {
if ((int)a.size() > p) return false;
int cnt = 0;
for (auto it: a) {
for (int v: adj[it]) {
if (a.find(v) != a.end())
continue;
cnt++;
if (cnt > q) return false;
}
}
return (cnt <= q);
}
void dfs(int u, ht& in, int root) {
if (!arr[root].empty() || (int)in.size() > p) return;
if ((int)in.size() <= p && valid(in)) {
arr[root] = in;
return;
}
for (auto it: in) {
for (int v: adj[it]) {
if (in.find(v) != in.end() || adj[v].size() > p + q)
continue;
in.insert(v);
dfs(v, in, root);
if (!arr[root].empty())
return;
in.erase(v);
}
}
}
int main() {
assert(3 == scanf("%d %d %d", &n, &p, &q));
int cnt = 0;
for (int i = 0; i < n; i++) {
int d;
assert(1 == scanf("%d", &d));
for (int j = 0; j < d; j++) {
int u;
assert(1 == scanf("%d", &u));
adj[i].pb(u);
if (mrk[u][i]) mrk[i][u] = mrk[u][i];
else mrk[i][u] = ++cnt;
}
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if ((mrk[i][j] && !mrk[j][i]) || (mrk[j][i] && !mrk[i][j])) {
printf("detention\n");
return 0;
}
for (int i = 0; i < n; i++) {
ht in; in.insert(i);
dfs(i, in, i);
if (arr[i].empty()) {
printf("detention\n");
return 0;
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
ht a = arr[j];
for (auto it: arr[i])
if (a.find(it) != a.end())
a.erase(it);
if (valid(a)) {
arr[j] = a;
continue;
}
a = arr[i];
for (auto it: arr[j])
if (a.find(it) != a.end())
a.erase(it);
arr[i] = a;
}
}
printf("home\n");
cnt = n;
for (int i = 0; i < n; i++) if (arr[i].empty()) cnt--;
printf("%d\n", cnt);
for (int i = 0; i < n; i++) {
if (arr[i].empty()) continue;
printf("%d ", (int)arr[i].size());
for (int j: arr[i])
printf("%d ", j);
printf("\n");
}
}
Compilation message
friends.cpp: In function 'void dfs(int, ht&, int)':
friends.cpp:62:57: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (in.find(v) != in.end() || adj[v].size() > p + q)
~~~~~~~~~~~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
888 KB |
Output is correct |
| 2 |
Correct |
5 ms |
888 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1016 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1016 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1016 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1016 KB |
Output is correct |
| 7 |
Correct |
5 ms |
1016 KB |
Output is correct |
| 8 |
Correct |
5 ms |
1016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
888 KB |
Output is correct |
| 2 |
Execution timed out |
1048 ms |
1528 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
888 KB |
Output is correct |
| 2 |
Execution timed out |
1048 ms |
1528 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
888 KB |
Output is correct |
| 2 |
Correct |
5 ms |
888 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1016 KB |
Output is correct |
| 4 |
Correct |
6 ms |
1016 KB |
Output is correct |
| 5 |
Correct |
6 ms |
1016 KB |
Output is correct |
| 6 |
Correct |
6 ms |
1016 KB |
Output is correct |
| 7 |
Correct |
5 ms |
1016 KB |
Output is correct |
| 8 |
Correct |
5 ms |
1016 KB |
Output is correct |
| 9 |
Correct |
5 ms |
888 KB |
Output is correct |
| 10 |
Execution timed out |
1048 ms |
1528 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
