#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( multiset <int> candidates, set<int> uniqueCandidates, set <int> chosen, int p, int q ) {
if ( uniqueCandidates.size() > p + q )
return;
if ( candidates.size() == 0 ) {
if ( chosen.size() > solution.size() )
solution = chosen;
return;
}
int v = *candidates.begin();
if ( p > 0 ) {
multiset <int> newCandidates = candidates;
set<int> newUniqueCandidates = uniqueCandidates;
set <int> newChosen = chosen;
newCandidates.erase( v );
newUniqueCandidates.erase( v );
newChosen.insert( v );
for ( int u: adj[v] ) {
if ( chosen.find( u ) == chosen.end() ) {
newCandidates.insert( u );
newUniqueCandidates.insert( u );
}
}
findGroup( newCandidates, newUniqueCandidates, newChosen, p - 1, q );
}
if ( q > 0 ) {
multiset <int> newCandidates = candidates;
set<int> newUniqueCandidates = uniqueCandidates;
set <int> newChosen = chosen;
newCandidates.erase( newCandidates.lower_bound( v ) );
if ( newCandidates.find( v ) == newCandidates.end() )
newUniqueCandidates.erase( v );
findGroup( newCandidates, newUniqueCandidates, newChosen, 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 ) {
for ( int v: a ) {
for ( int u: adj[v] ) {
if ( a.find( u ) == a.end() )
q--;
}
}
return (q >= 0);
}
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;
multiset <int> candidates;
set<int> uniqueCandidates;
set <int> chosen;
candidates.insert( u );
uniqueCandidates.insert( u );
solution.clear();
findGroup( candidates, uniqueCandidates, chosen, p, q );
if ( solution.size() == 0 ) {
cout << "detention\n";
cout << u << "\n";
return 0;
}
for ( int v: solution ) {
vis[v] = true;
frecv[v].push_back( u );
group[u].insert( v );
}
}
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 if ( check( b2, q ) ) {
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: group[u] )
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::multiset<int>, std::set<int>, std::set<int>, int, int)':
friends.cpp:14:34: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
14 | if ( uniqueCandidates.size() > p + q )
| ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
friends.cpp: In function 'int main()':
friends.cpp:84:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
84 | if ( adj[u].size() > p + q - 1 ) {
| ~~~~~~~~~~~~~~^~~~~~~~~~~
friends.cpp:120:16: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
120 | int x, y;
| ^
friends.cpp:120:13: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
120 | int x, y;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
0 ms |
600 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
0 ms |
856 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
600 KB |
Extra information in the output file |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
3 ms |
860 KB |
Output is correct |
| 3 |
Correct |
1 ms |
860 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
860 KB |
Extra information in the output file |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
3 ms |
860 KB |
Output is correct |
| 3 |
Correct |
1 ms |
860 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
860 KB |
Extra information in the output file |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Correct |
0 ms |
600 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
0 ms |
856 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
600 KB |
Extra information in the output file |
| 7 |
Halted |
0 ms |
0 KB |
- |
