#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2500;
int n;
vector<int> adj[MAX_N];
unordered_map<int, bool> isAdj[MAX_N];
set<int> solution, group[MAX_N];
vector<int> frecv[MAX_N];
bool vis[MAX_N];
void findGroup( set<int> candidates, set<int> chosen, set<int> refused, int p, int q ) {
/*cout << "stare\n";
cout << "sz ";
cout << candidates.size() << "\n";
for ( int v: candidates )
cout << v << " ";
cout << "\n";
cout << "sz ";
cout << chosen.size() << "\n";
for ( int v: chosen )
cout << v << " ";
cout << "\n";
cout << "sz ";
cout << refused.size() << "\n";
for ( int v: refused )
cout << v << " ";
cout << "\n";
cout << "\n\n";*/
if ( candidates.size() == 0 ) {
if ( chosen.size() > solution.size() )
solution = chosen;
return;
}
if ( candidates.size() > p + q )
return;
for ( int v: candidates ) {
if ( p > 0 ) {
set <int> newCandidates = candidates, newChosen = chosen, newRefused = refused;
newCandidates.erase( v );
newChosen.insert( v );
for ( int u: adj[v] ) {
if ( chosen.find( u ) == chosen.end() && refused.find( u ) == refused.end() )
newCandidates.insert( u );
}
findGroup( newCandidates, newChosen, newRefused, p - 1, q );
}
if ( q > 0 ) {
set <int> newCandidates = candidates, newChosen = chosen, newRefused = refused;
newCandidates.erase( v );
newRefused.insert( v );
findGroup( newCandidates, newChosen, newRefused, p, q - 1 );
}
}
}
bool verif() {
for ( int v = 0; v < n; v++ ) {
if ( frecv[v].size() > 1 )
return false;
}
return true;
}
bool check( set<int> a, int q ) {
set<int> c;
for ( int v: a ) {
for ( int u: adj[v] )
c.insert( u );
}
return (c.size() - a.size() <= q);
}
int main() {
int p, q;
cin >> n >> p >> q;
for ( int u = 0; u < n; u++ ) {
int k;
cin >> k;
for ( int i = 0; i < k; i++ ) {
int v;
cin >> v;
adj[u].push_back( v );
isAdj[u][v] = true;
}
}
for ( int u = 0; u < n; u++ ) {
if ( adj[u].size() > p + q - 1 ) {
cout << "detention\n";
return 0;
}
for ( int v: adj[u] ) {
if ( (isAdj[u][v] ^ isAdj[v][u]) == 1 ) {
cout << "detention\n";
return 0;
}
}
}
for ( int u = 0; u < n; u++ ) {
if ( vis[u] )
continue;
set<int> candidates, chosen, refused;
candidates.insert( u );
solution.clear();
findGroup( candidates, chosen, refused, p, q );
if ( solution.size() == 0 ) {
cout << "detention\n";
return 0;
}
//cout << u << "\n";
for ( int v: solution ) {
//cout << v << " ";
vis[v] = true;
frecv[v].push_back( u );
group[u].insert( v );
}
//cout << "\n\n";
}
while ( !verif() ) {
int x, y;
for ( int v = 0; v < n; v++ ) {
if ( frecv[v].size() > 1 ) {
x = frecv[v][0], y = frecv[v][1];
break;
}
}
set<int> a = group[x], b = group[y];
set<int> a1 = a, b1 = b;
for ( int v: b1 )
a1.erase( v );
set<int> a2 = a, b2 = b;
for ( int v: a2 )
b2.erase( v );
if ( check( a1, q ) ) {
group[x] = a1;
group[y] = b1;
} else {
group[x] = a2;
group[y] = b2;
}
for ( int v = 0; v < n; v++ )
frecv[v].clear();
for ( int u = 0; u < n; u++ ) {
for ( int v: solution )
frecv[v].push_back( u );
}
}
int ans = 0;
for ( int u = 0; u < n; u++ ) {
if ( group[u].size() > 0 )
ans++;
}
cout << "home\n";
cout << ans << "\n";
for ( int u = 0; u < n; u++ ) {
if ( group[u].size() == 0 )
continue;
cout << group[u].size() << " ";
for ( int v: group[u] )
cout << v << " ";
cout << "\n";
}
return 0;
}
Compilation message
friends.cpp: In function 'void findGroup(std::set<int>, std::set<int>, std::set<int>, int, int)':
friends.cpp:37:28: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
37 | if ( candidates.size() > p + q )
| ~~~~~~~~~~~~~~~~~~^~~~~~~
friends.cpp: In function 'bool check(std::set<int>, int)':
friends.cpp:75:33: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
75 | return (c.size() - a.size() <= q);
| ~~~~~~~~~~~~~~~~~~~~^~~~
friends.cpp: In function 'int main()':
friends.cpp:93:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
93 | if ( adj[u].size() > p + q - 1 ) {
| ~~~~~~~~~~~~~~^~~~~~~~~~~
friends.cpp:128:16: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
128 | int x, y;
| ^
friends.cpp:128:13: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
128 | int x, y;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Execution timed out |
1089 ms |
604 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Execution timed out |
1070 ms |
860 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Execution timed out |
1070 ms |
860 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Execution timed out |
1089 ms |
604 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
